Two-coloring cubic graphs with small monochromatic components, but without singletons

@misc{barat2026twocoloring,
  title = {{Two-coloring cubic graphs with small monochromatic components, but without singletons}},
  author = {János Barát and Zoltán L. Blázsik},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.30893},
  eprint = {2609.30893},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.30893},
}

TY  - UNPB
TI  - Two-coloring cubic graphs with small monochromatic components, but without singletons
AU  - János Barát
AU  - Zoltán L. Blázsik
PY  - 2026
DA  - 2026/09/25
PB  - arXiv
DO  - 10.48550/arxiv.2609.30893
UR  - https://arxiv.org/abs/2609.30893
AB  - We combine two coloring aspects that work in opposite directions. One can 2-color the vertices of a cubic graph such that each monochromatic component is very small. One can also 2-color the vertices of a cubic graph such that each monochromatic component has degree at least 1. As an intended tool for solving a special case of Wegner's conjecture, Thomassen formulated a conjecture that combined the two previous properties. This led to the concept of a crumby coloring. However it turned out that there are cubic graphs without such coloring. Here we try to see what natural relaxations of the original concept might hold for each cubic graph. We show there exists a constant c such that every cubic graph has a vertex 2-coloring such that every monochromatic component has at least 2 and at most c vertices. We also prove an unbalanced version, which is the natural relaxation of the crumby coloring.
ER  -