zbMATH — the first resource for mathematics

Relaxed two-coloring of cubic graphs. (English) Zbl 1118.05029
Summary: 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-class induces monochromatic components of order at most 750. 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.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Alon, N.; Ding, G.; Oporowski, B.; Vertigan, D., Partitioning into graphs with only small components, J. combin. theory ser. B, 87, 231-243, (2003) · Zbl 1023.05045
[2] Berke, R.; Szabó, T., Relaxed two-colorings of cubic graphs · Zbl 1209.05071
[3] G. Ding, B. Oporowski, D. Sanders, D. Vertigan, preprint
[4] Erdős, P.; Sachs, H., Reguläre graphen gegebener taillenweite mit minimaler knotenzahl, Wiss. Z. martin-luther-univ. halle-Wittenberg math. natur. reihe, 12, 251-257, (1963) · Zbl 0116.15002
[5] Haxell, P.; Szabó, T.; Tardos, G., Bounded size components—partitions and transversals, J. combin. theory ser. B, 88, 2, 281-297, (2003) · Zbl 1033.05083
[6] Jackson, B.; Wormald, N., On the linear k-arboricity of cubic graphs, Discrete math., 162, 293-297, (1996) · Zbl 0870.05036
[7] A. Kostochka, personal communication
[8] Lovász, L., On decomposition of graphs, Studia sci. math. hungar., 1, 237-238, (1966) · Zbl 0151.33401
[9] Thomassen, C., Two-colouring the edges of a cubic graph such that each monochromatic component is a path of length at most 5, J. combin. theory ser. B, 75, 100-109, (1999) · Zbl 0930.05043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.