Robert Berke ; Tibor Szabó - Relaxed Two-Coloring 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 Two-Coloring of Cubic Graphs

Authors: Robert Berke 1; Tibor Szabó 1

  • 1 Department of Computer Science [ETH Zürich]

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.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: Vertex coloring,bounded size components,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1705.06928
Source : ScholeXplorer IsRelatedTo DOI 10.1002/jgt.22462
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1705.06928
  • 10.1002/jgt.22462
  • 10.1002/jgt.22462
  • 1705.06928
  • 10.48550/arxiv.1705.06928
Colourings of cubic graphs inducing isomorphic monochromatic subgraphs

Consultation statistics

This page has been seen 140 times.
This article's PDF has been downloaded 310 times.