Cycles and new bounds for the chromatic number

In 1976, Bondy proved that the chromatic number of a graph G is at most its circumference, the length of a longest cycle. In 1992, Tuza proved that, for any integer k≥2, if a graph G contains no cycle of length congruent to 1 modulo k, then χ(G)≤k. In this paper, we use a DFS tree of a connected gra...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2023-03, Vol.346 (3), p.113255, Article 113255
Main Authors: Cordero-Michel, Narda, Galeana-Sánchez, Hortensia, Goldfeder, Ilan A.
Format: Article
Language:English
Subjects:
Chromatic number
DFS algorithm
Proper coloring
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In 1976, Bondy proved that the chromatic number of a graph G is at most its circumference, the length of a longest cycle. In 1992, Tuza proved that, for any integer k≥2, if a graph G contains no cycle of length congruent to 1 modulo k, then χ(G)≤k. In this paper, we use a DFS tree of a connected graph G to give proper colorings of V(G), based on the non-tree edges of the corresponding DFS tree and the cycle lengths of G. This method allows us to obtain improvements of the bounds proposed by Bondy and Tuza, respectively. Moreover, the hypotheses of most theorems presented in this paper can be checked in polynomial time.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2022.113255