Home » Subject » Graph Theory » Topological G.T. » Coloring
Importance: Medium ✭✭
Author(s): Alon, Noga
Ding, Guoli
Oporowski, Bogdan
Vertigan, Dirk
Subject: Graph Theory
» Topological Graph Theory
» » Coloring
Keywords: coloring
partition
planar graph
Recomm. for undergrads: yes
Posted by: mdevos
on: May 23rd, 2007
Solved by: Louis Esperet, Gwenaël Joret [arXiv:1303.2487]
Question   Does there exists a fixed function $ f : {\mathbb N} \rightarrow {\mathbb N} $ so that every planar graph of maximum degree $ d $ has a partition of its vertex set into at most three sets $ \{V_1,V_2,V_3\} $ so that for $ i=1,2,3 $, every component of the graph induced by $ V_i $ has size at most $ f(d) $?

An ordinary $ k $-coloring of a graph, is a partition the vertex set into at most $ k $ sets $ \{V_1,\ldots,V_k\} $ so that each $ V_i $ induces a subgraph where every component is an isolated vertex. Here we are considering a relaxation of this where we insist only that each $ V_i $ 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 $ \{V_1,\ldots,V_4\} $ so that every component of a subgraph induced by some $ V_i $ has size at most 1. On the other hand, Alon, Ding, Oporowski, and Vertigan construct for every integer $ n $ a planar graph $ G_n $ with the property that for every partition of $ V(G_n) $ into $ \{V_1,V_2,V_3\} $, some component of a subgraph induced by some $ V_i $ will have size $ \ge n $. The construction is easy to give: Let $ H $ be the graph obtained from a path $ P $ of length $ n^2 $ by adding a new vertex $ u $ adjacent to every vertex of this path. Now, form the graph $ G_n $ from $ n $ disjoint copies of $ H $ by adding a new vertex $ v $ joined to every old vertex. Note that $ G_n $ is planar as required. Let us assume (for a contradiction) that $ \{V_1,V_2,V_3\} $ is a partition of $ V(G) $ with the property that every component of a subgraph induced by $ V_i $ has size $ <n $. We may assume without loss that $ v \in V_3 $, but then there are at most $ n-2 $ other vertices in $ V_3 $, so there is a copy of $ H $ which contains no vertices in $ V_3 $. We may assume that the vertex $ u $ in this copy is in the set $ V_2 $, but then at most $ n-2 $ other vertices in the corresponding copy of $ P $ are in $ V_2 $. It now follows that there is a subpath of this copy of $ P $ of length $ \ge n $ in which all vertices are in $ V_1 $. 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.
add new comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options