From semi-total to equitable total colorings
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916001351729152 |
|---|---|
| author | Dejter, I. J. |
| author_facet | Dejter, I. J. |
| contents | Independently posed by Behzad and Vizing, the Total Coloring Conjecture asserts that the total chromatic number of a simple connected graph $G$ is either $Δ(G)+1$ or $Δ(G)+2$, where $Δ(G)$ is the largest degree of any vertex of $G$.
To decide whether a cubic graph $G$ has total chromatic number $Δ(G)+1$, even for bipartite cubic graphs, is NP-hard. The resulting problems and research persist even for total colorings that are equitable, namely with the cardinalities of the color classes differing at most by 1. Williams and Holroyd gave a new condition to solve total coloring problems via the introduction of semi-total colorings. We focus on how to obtain equitable total colorings of symmetric cubic graphs and cage graphs by means of a variation of Kempe'a 1879 graph-coloring algorithm. Such variation takes semi-total colorings to equitable ones. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_20055 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | From semi-total to equitable total colorings Dejter, I. J. Combinatorics 05C15, 05C38, 05C69, 05C90, 94B25 Independently posed by Behzad and Vizing, the Total Coloring Conjecture asserts that the total chromatic number of a simple connected graph $G$ is either $Δ(G)+1$ or $Δ(G)+2$, where $Δ(G)$ is the largest degree of any vertex of $G$. To decide whether a cubic graph $G$ has total chromatic number $Δ(G)+1$, even for bipartite cubic graphs, is NP-hard. The resulting problems and research persist even for total colorings that are equitable, namely with the cardinalities of the color classes differing at most by 1. Williams and Holroyd gave a new condition to solve total coloring problems via the introduction of semi-total colorings. We focus on how to obtain equitable total colorings of symmetric cubic graphs and cage graphs by means of a variation of Kempe'a 1879 graph-coloring algorithm. Such variation takes semi-total colorings to equitable ones. |
| title | From semi-total to equitable total colorings |
| topic | Combinatorics 05C15, 05C38, 05C69, 05C90, 94B25 |
| url | https://arxiv.org/abs/2503.20055 |