The chromatic number of a graph with two odd holes and an odd girth (Q6143691)
From MaRDI portal
scientific article; zbMATH DE number 7783962
Language | Label | Description | Also known as |
---|---|---|---|
English | The chromatic number of a graph with two odd holes and an odd girth |
scientific article; zbMATH DE number 7783962 |
Statements
The chromatic number of a graph with two odd holes and an odd girth (English)
0 references
5 January 2024
0 references
For \(\ell \geq 2\), let \({\mathcal{H}}_\ell\) denote the family of graphs that have girth \(2\ell +1\) and have no induced odd cycles of length different from \(2\ell+1\). Moreover, \({\mathcal{G}}_\ell\) denotes the family of graphs \(G\) that have girth \(2\ell+1\) and any induced odd cycle in \(G\) is of length \(2\ell+1\) or \(2\ell+3\). In the last few years the chromatic number of graphs in \({\mathcal{H}}_\ell\) was intensively studied. \textit{B. Xu} et al. [Electron. J. Comb. 24, No. 4, Research Paper P4.32, 8 p. (2017; Zbl 1373.05071)] proved that graphs in \({\mathcal{H}}_2\) are 4-colorable. This result was just recently improved by \textit{M. Chudnovsky} and \textit{P. Seymour} [J. Graph Theory 103, No. 3, 437--450 (2023; Zbl 1522.05237)] who proved that graphs in \({\mathcal{H}}_2\) are 3-colorable. Moreover, \textit{W. Di} et al. [``The chromatic number of heptagraphs'', Preprint, arXiv:2206.01400 [math.CO] (2022)] proved that graphs in \({\mathcal{H}}_3\) are also 3-colorable. In this paper, the authors study the chromatic number of a larger family, namely the chromatic number of graphs in \({\mathcal{G}}_\ell\). They prove that for an integer \(\ell \geq 3\) any connected graph \(G \in {\mathcal{G}}_\ell\) has the property that the subgraph of \(G\), induced by the set of vertices that have the same distance to some fixed vertex, is bipartite. This result immediately implies that all graphs in \({\mathcal{G}}_\ell\), for \(\ell \geq 3\), are 4-colorable. Finally, they show that each graph in \(\bigcup_{\ell \geq 3}{\mathcal{G}}_\ell\) with radius at most \(\ell\) is 3-colorable. The authors conclude the paper with an open problem about an upper bound for the chromatic number of graphs in \({\mathcal{G}}_2\).
0 references
chromatic number
0 references
girth
0 references
odd hole
0 references