An even hole is an induced cycle of even length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this talk, we consider (cap, even hole)-free graphs, i.e., graphs that do not contain any even hole or cap as an induced subgraph.

We will first give a decomposition theorem for the class of (cap, even hole)-free graphs, and then show how  to use the decomposition theorem to obtain (1) every (cap, even hole)-free graph has chromatic number at most 1.5 times its clique number; (2) the first polynomial time algorithm for finding the chromatic number for those graphs.


Shenwei Huang

Research Area

UNSW, School of Computer Science and Engineering



Thu, 13/04/2017 - 1:00pm


RC-4082, The Red Centre, UNSW