# Relaxed Two-Coloring of Cubic Graphs

Abstract : We 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [6 references]

https://hal.inria.fr/hal-01184434
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 2:58:42 PM
Last modification on : Thursday, May 27, 2021 - 1:54:05 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:11:17 AM

### File

dmAE0166.pdf
Publisher files allowed on an open archive

### Identifiers

• HAL Id : hal-01184434, version 1

### Citation

Robert Berke, Tibor Szabó. Relaxed Two-Coloring of Cubic Graphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.341-344. ⟨hal-01184434⟩

Record views