Claw-free cubic graphs are $(1, 1, 2, 2)$-colorable
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917784245501952 |
|---|---|
| author | Brešar, Boštjan Kuenzel, Kirsti Rall, Douglas F. |
| author_facet | Brešar, Boštjan Kuenzel, Kirsti Rall, Douglas F. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15455 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Claw-free cubic graphs are $(1, 1, 2, 2)$-colorable Brešar, Boštjan Kuenzel, Kirsti Rall, Douglas F. Combinatorics 05C15, 05C12 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. |
| title | Claw-free cubic graphs are $(1, 1, 2, 2)$-colorable |
| topic | Combinatorics 05C15, 05C12 |
| url | https://arxiv.org/abs/2409.15455 |