Importance: Medium ✭✭
 Author(s): Alon, Noga Ding, Guoli Oporowski, Bogdan Vertigan, Dirk
 Subject: Graph Theory » Topological Graph Theory » » Coloring
 Keywords: coloring partition planar graph
 Posted by: mdevos on: May 23rd, 2007
 Solved by: Louis Esperet, Gwenaël Joret [arXiv:1303.2487]
Question   Does there exists a fixed function so that every planar graph of maximum degree has a partition of its vertex set into at most three sets so that for , every component of the graph induced by has size at most ?

An ordinary -coloring of a graph, is a partition the vertex set into at most sets so that each induces a subgraph where every component is an isolated vertex. Here we are considering a relaxation of this where we insist only that each induces a subgraph where every component has bounded size. This type of coloring was first suggested by Ding, Oporowski, and Vertigan and has already lead to some interesting results see [ADOV] and [HSzT].

It follows from the four color theorem that every planar graph has a vertex partition into four sets so that every component of a subgraph induced by some has size at most 1. On the other hand, Alon, Ding, Oporowski, and Vertigan construct for every integer a planar graph with the property that for every partition of into , some component of a subgraph induced by some will have size . The construction is easy to give: Let be the graph obtained from a path of length by adding a new vertex adjacent to every vertex of this path. Now, form the graph from disjoint copies of by adding a new vertex joined to every old vertex. Note that is planar as required. Let us assume (for a contradiction) that is a partition of with the property that every component of a subgraph induced by has size . We may assume without loss that , but then there are at most other vertices in , so there is a copy of which contains no vertices in . We may assume that the vertex in this copy is in the set , but then at most other vertices in the corresponding copy of are in . It now follows that there is a subpath of this copy of of length in which all vertices are in . This completes the proof. The above question asks if such a family can still be constructed with the additional constraint that all vertices have bounded degree.

In 2013, this question was answered in the affirmative by Louis Esperet and Gwenaël Joret [EJ].

## Bibliography

*[ADOV] Alon, Noga; Ding, Guoli; Oporowski, Bogdan; Vertigan, Dirk, Partitioning into graphs with only small components, J. Combin. Theory Ser. B 87 (2003), no. 2, 231--243. MathSciNet

[HSzT] Haxell, Penny; Szabó, Tibor; Tardos, Gábor, Bounded size components - partitions and transversals. J. Combin. Theory Ser. B 88 (2003), no. 2, 281--297. MathSciNet

[EJ] Louis Esperet, Gwenaël Joret. Coloring planar graphs with three colors and no large monochromatic components, arXiv:1303.2487, 2013.

* indicates original appearance(s) of problem.