Some Remarks on Even-Hole-Free Graphs

Abstract

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 Chudnovsky and Seymour 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\geq s >  \chi(G)/3$;    every $9$-chromatic graph $G$ with $\omega(G)\leq 8$ has a $K_4\cup K_6$ minor;  for all $k\geq 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 on even-hole-free graphs.