https://hal.inria.fr/hal-01184434Berke, RobertRobertBerkeD-INFK - Department of Computer Science [ETH Zürich] - ETH Zürich - Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich]Szabó, TiborTiborSzabóD-INFK - Department of Computer Science [ETH Zürich] - ETH Zürich - Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich]Relaxed Two-Coloring of Cubic GraphsHAL CCSD2005Vertex coloringbounded size components[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM][MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]Episciences Iam, CoordinationStefan Felsner2015-08-14 14:58:422021-05-27 13:54:052015-08-17 09:27:51enConference papershttps://hal.inria.fr/hal-01184434/document10.46298/dmtcs.3445application/pdf1We show that any graph of maximum degree at most $3$ has a two-coloring, such that one color-class 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.