Claw-free cubic graphs are $(1, 1, 2, 2)$-colorable
| Autor: | Brešar, Boštjan, Kuenzel, Kirsti, Rall, Douglas F. |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | A $(1,1,2,2)$-coloring of a graph is a partition of its vertex set into four sets two of which are independent and the other two are $2$-packings. In this paper, we prove that every claw-free cubic graph admits a $(1,1,2,2)$-coloring. This implies that the conjecture from [Packing chromatic number, $(1,1,2,2)$-colorings, and characterizing the Petersen graph, Aequationes Math.\ 91 (2017) 169--184] that the packing chromatic number of subdivisions of subcubic graphs is at most $5$ is true in the case of claw-free cubic graphs. Comment: 12 pages, 2 figures, 17 references |
| Databáze: | arXiv |
| Externí odkaz: |
|