Coloring certain even-hole-free graphs

This talk will consist of three parts.

In the first part of the talk (joint work with Valerio Boncompagni and Kristina Vušković), we present some recent structural and algorithmic results for several classes of graphs defined by forbidding certain “Truemper configurations” as induced subgraphs. (A _Truemper configuration_ is any theta, pyramid, prism, or wheel.)

In the second part of the talk (joint work with Frédéric Maffray and Kristina Vušković), we present a polynomial-time coloring algorithm for “rings.” A ring is a certain generalization of a hyperhole, and it has the property that all holes in it are of the same length. (A _hole_ is an induced cycle of length at least four.) Rings originally appeared as a “basic” class in decomposition theorems for a couple of classes discussed in the first part of the talk.

In the third part of the talk, we discuss the structure of even-hole-free graphs of stability number at most three, and we present a polynomial-time coloring algorithm for these graphs.

The seminar will be broadcasting via Zoom through the following link:

Join Zoom Meeting

https://upr-si.zoom.us/j/85914318577?pwd=cnFJcmg2ZEZkbFhpeG1VYk0veHp2Zz09