Total coloring of regular graphs of girth = degree + 1
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913830219546624 |
|---|---|
| author | Dejter, Italo J. |
| author_facet | Dejter, Italo J. |
| contents | Let $2\le k\in\mathbb{Z}$. A total coloring of a $k$-regular simple graph via $k+1$ colors is an {\it efficient total coloring} if each color yields an efficient dominating set, where the efficient domination condition applies to the restriction of each color class to the vertex set. In this work, focus is set upon graphs of girth $k+1$. Efficient total colorings of finite connected simple cubic graphs of girth 4 are constructed starting at the 3-cube. It is conjectured that all of them are obtained by means of four basic operations. In contrast, the Robertson 19-vertex $(4,5)$-cage, the alternate union $Pet^k$ of a (Hamilton) $10k$-cycle with $k$ pentagon and $k$-pentagram $5$-cycles, for $k>1$ not divisible by 5, and its double cover $Dod^k$, contain TCs that are nonefficient. Applications to partitions into 3-paths and 3-stars are given. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_08781 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Total coloring of regular graphs of girth = degree + 1 Dejter, Italo J. Combinatorics 05C15, 05C69, 05C70, 05C38, 94B25 Let $2\le k\in\mathbb{Z}$. A total coloring of a $k$-regular simple graph via $k+1$ colors is an {\it efficient total coloring} if each color yields an efficient dominating set, where the efficient domination condition applies to the restriction of each color class to the vertex set. In this work, focus is set upon graphs of girth $k+1$. Efficient total colorings of finite connected simple cubic graphs of girth 4 are constructed starting at the 3-cube. It is conjectured that all of them are obtained by means of four basic operations. In contrast, the Robertson 19-vertex $(4,5)$-cage, the alternate union $Pet^k$ of a (Hamilton) $10k$-cycle with $k$ pentagon and $k$-pentagram $5$-cycles, for $k>1$ not divisible by 5, and its double cover $Dod^k$, contain TCs that are nonefficient. Applications to partitions into 3-paths and 3-stars are given. |
| title | Total coloring of regular graphs of girth = degree + 1 |
| topic | Combinatorics 05C15, 05C69, 05C70, 05C38, 94B25 |
| url | https://arxiv.org/abs/2405.08781 |