Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case (Q2363699)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case |
scientific article |
Statements
Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case (English)
0 references
26 July 2017
0 references
Summary: In this paper, we prove that the class of graphs with no triangle and no induced cycle of even length at least 6 has bounded chromatic number. It is well-known that even-hole-free graphs are \(\chi\)-bounded but we allow here the existence of \(C_4\). The proof relies on the concept of parity changing path, an adaptation of trinity changing path which was recently introduced by \textit{M. Bonamy} [``Graphs with large chromatic number induce 3k-cycles'', Preprint, \url{arXiv:1408.2172}] to prove that graphs with no induced cycle of length divisible by three have bounded chromatic number.
0 references
graph coloring
0 references
forbidding cycles
0 references
even hole
0 references
trinity changing path
0 references
0 references