Geodesic
On Vizing's problem for triangle-free graphs
The electronic journal of combinatorics, Tome 32 (2025) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We prove that $\chi(G) \le \lceil (\Delta+1)/2\rceil+1$ for any triangle-free graph $G$ of maximum degree $\Delta$ provided $\Delta \ge 524$. This gives tangible progress towards an old problem of Vizing, in a form cast by Reed. We use a method of Hurley and Pirot, which in turn relies on a new counting argument of the second author.
DOI : 10.37236/12703
Classification : 05C15, 05C35, 05C07
Mots-clés : chromatic number, clique 
@article{10_37236_12703,
     author = {Ross J. Kang and Matthieu Rosenfeld},
     title = {On {Vizing's} problem for triangle-free graphs},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {4},
     doi = {10.37236/12703},
     zbl = {8120089},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/12703/}
}
TY  - JOUR
AU  - Ross J. Kang
AU  - Matthieu Rosenfeld
TI  - On Vizing's problem for triangle-free graphs
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/12703/
DO  - 10.37236/12703
ID  - 10_37236_12703
ER  - 
%0 Journal Article
%A Ross J. Kang
%A Matthieu Rosenfeld
%T On Vizing's problem for triangle-free graphs
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/12703/
%R 10.37236/12703
%F 10_37236_12703
Ross J. Kang; Matthieu Rosenfeld. On Vizing's problem for triangle-free graphs. The electronic journal of combinatorics, Tome 32 (2025) no. 4. doi: 10.37236/12703

Cité par Sources :