A caterpillar is either a K2 or a tree on at least 3 vertices such that deleting its leaves we obtain a path of order at least 1. Given a simple undirected graph G=(V,E), a caterpillar factor of G is a set of caterpillar subgraphs of G such that each vertex v∈V belongs to exactly one of them. A caterpillar factor F is internally even if every vertex of degree degF(v)≥2 has an even degree; F is odd if degF(v) is odd for every v∈V(G). We present a linear-time algorithm that decides whether a tree admits an internally even caterpillar factor and, on the other hand, we prove that the decision problem is NP-complete on the class of planar bipartite graphs. For the odd caterpillar factor problem, we obtain similar results. It can be decided in linear time over the class of trees, but the problem is NP-complete on the class of bipartite graphs.

We show that the maximum number of colors that can be used in a vertex coloring of a cubic 3-connected plane graph G that avoids a face with vertices of mutually distinct colors (a rainbow face) is equal to $\frac{n}{2}+\mu^*-2$, where n is the number of vertices of G and $\mu^*$ is the size of the maximum matching of the dual graph $G^*$.

Let G be a 3-connected plane graph. Plummer and Toft [ J. Graph Theory, 11 (1987), pp. 507--515] conjectured that $\chi_{c}(G) \leq \Delta^{*}(G) + 2$, where $\chi_{c}(G)$ is the cyclic chromatic number of G and $\Delta^{*}(G)$ the maximum face size of G. Hornák and Jendrol' [ J. Graph Theory, 30 (1999), pp. 177--189] and Borodin and Woodall [ SIAM J. Discrete Math., submitted] independently proved this conjecture when $\Delta^{*}(G)$ is large enough. Moreover, Borodin and Woodall proved a stronger statement that $\chi_{c}(G) \leq \Delta^{*}(G) + 1$ holds if $\Delta^{*}(G) \geq 122$. In this paper, we prove that $\chi_{c}(G) \leq \Delta^{*}(G) + 1$ holds if $\Delta^{*}(G)\geq 60$.