Atlas home || Conferences | Abstracts | about Atlas

21st Cumberland Conference on Graph Theory, Combinatorics, and Computing ---In Honor of Mike Plummer's 70th Birthday
May 15-17, 2008
Vanderbilt University
Nashville, TN, USA

Organizers
Mark Ellingham and Gexin Yu

View Abstracts
Conference Homepage

On K4-free graphs with no odd holes
by
Neil Robertson
Ohio State University
Coauthors: Maria Chudnovsky, Paul Seymour and Robin Thomas

A hole in a graph is a circuit of girth at least 4 and having no chords. Perfect graphs are simple graphs which have equality of maximum clique size and chromatic number, for all induced subgraphs. It is well known that perfect graphs are exactly those graphs G with no odd girth odd hole and with no odd girth hole in the edge-set complement G'. Holes in G' are called antiholes in G. This talk discusses a proof of a conjecture of G. Ding that graphs with no odd hole and no K4-subgraph have chromatic number 4. Some motivating open problems will also be discussed.

Date received: May 9, 2008

Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cawn-72.