*********************************** * Princeton Discrete Math Seminar * *********************************** Speaker: Shenwei Huang (Simon Fraser U.) Thursday 3rd May, 3:00 in Fine Hall 224. Title: Coloring (cap, even hole)-free graphs Abstract: An even cycle of length 4 or more is called an even hole. 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 first show how to decompose these graphs into (triangle, even hole)-free graphs. Using our decomposition theorem we prove that every such graph G has a vertex of degree at most 3/2 ω(G) − 1, and hence χ(G) ≤ 3/2 ω(G), where ω(G) denotes the size of a largest clique in G and χ(G) denotes the chromatic number of G. Finally, we give a polynomial-time algorithm for finding the chromatic number of these graphs. Our algorithm is based on our result that (triangle, even hole)-free graphs have tree-width at most 5.  Joint work with Kathie Cameron, Murilo da Silva and Kristina Vuskovic ---------------------------------- Next week: Martin Loebl Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)