Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
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


Publisher files allowed on an open archive




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, ⟨10.46298/dmtcs.3445⟩. ⟨hal-01184434⟩



Record views


Files downloads