A note on chromatic number and induced odd cycles
type: Item
instance of: scholarly article
title: A note on chromatic number and induced odd cycles
zbMATH Open document ID: 1373.05071
author: Gexin Yu
author: Xiaoya Zha
author: Baogang Xu
published in: The Electronic Journal of Combinatorics
publication date: 2017-11-10T00:00:00Z
full work available at URL: v24i4p32
review text: Summary: An odd hole is an induced odd cycle of length at least 5. \textit{A. D. Scott} and \textit{P. Seymour} [J. Comb. Theory, Ser. B 121, 68--84 (2016; Zbl 1412.05076)] confirmed a conjecture of \textit{A. Gyárfás} [Colloq. Math. Soc. János Bolyai 10, 801-816 (1975; Zbl 0307.05111)] and proved that if a graph \(G\) has no odd holes then \(\chi(G)\leqslant 2^{2^{\omega(G)+2}}\). \textit{M. Chudnovsky} et al. [J. Comb. Theory, Ser. B 100, No. 3, 313--331 (2010; Zbl 1274.05238)] showed that if \(G\) has neither \(K_4\) nor odd holes then \(\chi(G)\leqslant 4\). In this note, we show that if a graph \(G\) has neither triangles nor quadrilaterals, and has no odd holes of length at least 7, then \(\chi(G)\leqslant 4\) and \(\chi(G)\leqslant 3\) if \(G\) has radius at most \(3\), and for each vertex \(u\) of \(G\), the set of vertices of the same distance to \(u\) induces a bipartite subgraph. This answers some questions in [\textit{M. Plummer} and \textit{X. Zha}, Electron. J. Comb. 21, No. 1, Research Paper P1.34, 9 p. (2014; Zbl 1300.05149)].
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C17
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 6805097
zbMATH Keywords: chromatic number
zbMATH Keywords: induced odd cycles
MaRDI profile type: Publication
cites work: Q5570136
cites work: The strong perfect graph theorem
cites work: \(K_{4}\)-free graphs with no odd holes
cites work: Substitution and \(\chi\)-boundedness
cites work: Induced subgraphs of graphs with large chromatic number. XI. Orientations
cites work: Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
cites work: Graph Theory and Probability
cites work: Q5732334
cites work: Q4063176
cites work: Induced subtrees in graphs of large chromatic number
cites work: Q5749319
cites work: Radius two trees specify χ‐bounded classes
cites work: Radius Three Trees in Graphs with Large Chromatic Number
cites work: Sur le coloriage des graphs
cites work: On a conjecture concerning the Petersen graph
cites work: On a conjecture concerning the Petersen graph. II
cites work: Q3129824
cites work: Induced cycles and chromatic number
cites work: Induced subgraphs of graphs with large chromatic number. I. Odd holes
cites work: Induced subgraphs of graphs with large chromatic number. IV: Consecutive holes
cites work: Q3932997
Recommended article: A note on cyclic chromatic number
Recommended article: Induced cycles and chromatic number
Recommended article: Chromatic number, induced cycles, and non-separating cycles
Recommended article: Q5309554
Recommended article: Induced odd cycle packing number, independent sets, and chromatic number
Recommended article: A bound on the chromatic number using the longest odd cycle length
Recommended article: Q3410616
Recommended article: Q4636270
Recommended article: A Strengthening on Odd Cycles in Graphs of Given Chromatic Number
Recommended article: A note on \(n\)-edge chromatic number
description: scientific article; zbMATH DE number 6805097