Some remarks on even-hole-free graphs (Q2161221)

Summary: A vertex of a graph is bisimplicial if the set of its neighbors is the union of two cliques; a graph is quasi-line if every vertex is bisimplicial. A recent result of \textit{M. Chudnovsky} and \textit{P. Seymour} [``Even-hole-free graphs still have bisimplicial vertices'', Preprint, \url{arXiv:1909.10967}] asserts that every non-empty even-hole-free graph has a bisimplicial vertex. Both Hadwiger's conjecture and the Erdős-Lovász Tihany conjecture have been shown to be true for quasi-line graphs, but are open for even-hole-free graphs. In this note, we prove that every even-hole-free graph \(G\) with \(\omega(G)<\chi(G)=s+t-1\) satisfies the Erdős-Lovász Tihany conjecture provided that \(t\geqslant s > \chi(G)/3\); every \(9\)-chromatic graph \(G\) with \(\omega(G)\leqslant 8\) has a \(K_4\cup K_6\) minor; for all \(k\geqslant 7\), every even-hole-free graph with no \(K_k\) minor is \((2k-5)\)-colorable. Our proofs rely heavily on the structural result of Chudnovsky and Seymour [loc. cit.] on even-hole-free graphs.