Robert Berke ; Tibor Szabó

Relaxed TwoColoring of Cubic Graphs
dmtcs:3445 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

https://doi.org/10.46298/dmtcs.3445
Relaxed TwoColoring of Cubic GraphsArticle
Authors: Robert Berke ^{1}; Tibor Szabó ^{1}
NULL##NULL
Robert Berke;Tibor Szabó
1 Department of Computer Science [ETH Zürich]
We show that any graph of maximum degree at most $3$ has a twocoloring, such that one colorclass is an independent set while the other color induces monochromatic components of order at most $189$. On the other hand for any constant $C$ we exhibit a $4$regular graph, such that the deletion of any independent set leaves at least one component of order greater than $C$. Similar results are obtained for coloring graphs of given maximum degree with $k+ \ell$ colors such that $k$ parts form an independent set and $\ell$ parts span components of order bounded by a constant. A lot of interesting questions remain open.
Nathan Linial;JiŘÍ MatouŠek;Or Sheffet;GÁbor Tardos, 2008, Graph Colouring with No Large Monochromatic Components, Combinatorics, Probability & Computing, 17, 4, pp. 577589, 10.1017/s0963548308009140.