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 Hadwigers conjecture and the ErdH{o}s-Lovasz 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 for all $kge7$, every even-hole-free graph with no $K_k$ minor is $(2k-5)$-colorable; every even-hole-free graph $G$ with $omega(G)<chi(G)=s+t-1$ satisfies the ErdH{o}s-Lovasz Tihany conjecture provided that $ tge s> chi(G)/3$. Furthermore, we prove that every $9$-chromatic graph $G$ with $omega(G)le 8$ has a $K_4cup K_6$ minor. Our proofs rely heavily on the structural result of Chudnovsky and Seymour on even-hole-free graphs.
تحميل البحث