Total coloring graphs with large maximum degree
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909200717709312 |
|---|---|
| author | Dalal, Aseem McDonald, Jessica Shan, Songling |
| author_facet | Dalal, Aseem McDonald, Jessica Shan, Songling |
| contents | We prove that for any graph $G$, the total chromatic number of $G$ is at most $Δ(G)+2\left\lceil \frac{|V(G)|}{Δ(G)+1} \right\rceil$. This saves one color in comparison with a result of Hind from 1992. In particular, our result says that if $Δ(G)\ge \frac{1}{2}|V(G)|$, then $G$ has a total coloring using at most $Δ(G)+4$ colors. When $G$ is regular and has a sufficient number of vertices, we can actually save an additional two colors. Specifically, we prove that for any $0<\varepsilon <1$, there exists $n_0\in \mathbb{N}$ such that: if $G$ is an $r$-regular graph on $n \ge n_0$ vertices with $r\ge \frac{1}{2}(1+\varepsilon) n$, then $χ_T(G) \le Δ(G)+2$. This confirms the Total Coloring Conjecture for such graphs $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_07382 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Total coloring graphs with large maximum degree Dalal, Aseem McDonald, Jessica Shan, Songling Combinatorics 05C15 We prove that for any graph $G$, the total chromatic number of $G$ is at most $Δ(G)+2\left\lceil \frac{|V(G)|}{Δ(G)+1} \right\rceil$. This saves one color in comparison with a result of Hind from 1992. In particular, our result says that if $Δ(G)\ge \frac{1}{2}|V(G)|$, then $G$ has a total coloring using at most $Δ(G)+4$ colors. When $G$ is regular and has a sufficient number of vertices, we can actually save an additional two colors. Specifically, we prove that for any $0<\varepsilon <1$, there exists $n_0\in \mathbb{N}$ such that: if $G$ is an $r$-regular graph on $n \ge n_0$ vertices with $r\ge \frac{1}{2}(1+\varepsilon) n$, then $χ_T(G) \le Δ(G)+2$. This confirms the Total Coloring Conjecture for such graphs $G$. |
| title | Total coloring graphs with large maximum degree |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2405.07382 |