On Vizing’s Problem for Triangle-Free Graphs
Open Access
- 3 October 2025
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 32 (4) , P4.3
Abstract
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.
Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Asymmetric List Sizes in Bipartite GraphsAnnals of Combinatorics, 2021
- Coloring triangle‐free graphs with local list sizesRandom Structures & Algorithms, 2020
- The Johansson‐Molloy theorem for DP‐coloringRandom Structures & Algorithms, 2018
- Destroying Noncomplete Regular Components in Graph PartitionsJournal of Graph Theory, 2012
- The Repulsive Lattice Gas, the Independent-Set Polynomial, and the Lov sz Local LemmaJournal of Statistical Physics, 2005
- Graph Colouring and the Probabilistic Method2002
- Coloring Graphs with Sparse NeighborhoodsJournal of Combinatorial Theory, Series B, 1999
- The choice number of random bipartite graphsAnnals of Combinatorics, 1998
- Another bound on the chromatic number of a graphDiscrete Mathematics, 1978
- Covering the vertex set of a graph with subgraphs of smaller degreeDiscrete Mathematics, 1978