Logo image
Se connecter
On Vizing's problem for triangle-free graphs
Article de revue   Avec comité de lecture

On Vizing's problem for triangle-free graphs

Ross J. Kang et Matthieu Rosenfeld
The Electronic journal of combinatorics, Vol.32(4), 12703
03/10/2025

Résumé

Mathematics Mathematics, Applied Physical Sciences Science & Technology
We prove that chi(G) <= inverted right perpendicular(triangle+1)/2inverted left perpendicular +1 for any triangle-free graph G of maximum degree triangle provided triangle >= 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.

Indicateurs

1 Consultations de la notice

Détails

Logo image