Computer Science/Discrete Mathematics Seminar II

A graph is called {\em even-hole-free} if no induced subgraph of it is a cycle with an even number of vertices. A vertex of a graph is {\em bisimplicial} if the vertex set of its neighborhood can be partitioned into two cliques. Bruce Reed conjectured that every even-hole-free graph has a bisimplicial vertex. This, in particular, implies that the chromatic number of an even-hole-free graph is bounded by twice the size of its maximum clique. This provides further evidence of the connection between excluding certain induced subgraphs in a graph and the behavior of its chromatic number (similarly to perfect graphs, clawfree graphs, and others). Recently we were able to prove the conjecture. This result is joint with Paul Seymour, an partly joint with Bruce Reed.