Vu's conjecture holds for claw-free graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909887802376192 |
|---|---|
| author | Cook, Linda Kang, Ross J. Robinson, Eileen Zwaneveld, Gabriëlle |
| author_facet | Cook, Linda Kang, Ross J. Robinson, Eileen Zwaneveld, Gabriëlle |
| contents | Given a graph $G$, let $Δ_2(G)$ denote the maximum number of neighbors any two distinct vertices of $G$ have in common. Vu (2002) proposed that, provided $Δ_2(G)$ is not too small as a proportion of the maximum degree $Δ(G)$ of $G$, the chromatic number of $G$ should never be too much larger than $Δ_2(G)$. We make a first approach towards Vu's conjecture from a structural graph theoretic point of view. We prove that, in the case where $G$ is claw-free, indeed the chromatic number of $G$ is at most $Δ_2(G)+3$. This is tight, as our bound is met with equality for the line graph of the Petersen graph. Moreover, we can prove this in terms of the more specific parameter that bounds the maximum number of neighbors any two endpoints of some edge of $G$ have in common. Our result may be viewed as a generalization of the classic bound of Vizing (1964) for edge-coloring. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_15553 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Vu's conjecture holds for claw-free graphs Cook, Linda Kang, Ross J. Robinson, Eileen Zwaneveld, Gabriëlle Combinatorics 2020: 05C15, 05C75, 05C35 Given a graph $G$, let $Δ_2(G)$ denote the maximum number of neighbors any two distinct vertices of $G$ have in common. Vu (2002) proposed that, provided $Δ_2(G)$ is not too small as a proportion of the maximum degree $Δ(G)$ of $G$, the chromatic number of $G$ should never be too much larger than $Δ_2(G)$. We make a first approach towards Vu's conjecture from a structural graph theoretic point of view. We prove that, in the case where $G$ is claw-free, indeed the chromatic number of $G$ is at most $Δ_2(G)+3$. This is tight, as our bound is met with equality for the line graph of the Petersen graph. Moreover, we can prove this in terms of the more specific parameter that bounds the maximum number of neighbors any two endpoints of some edge of $G$ have in common. Our result may be viewed as a generalization of the classic bound of Vizing (1964) for edge-coloring. |
| title | Vu's conjecture holds for claw-free graphs |
| topic | Combinatorics 2020: 05C15, 05C75, 05C35 |
| url | https://arxiv.org/abs/2510.15553 |