Agenda de l'ENS de Lyon

Graphs are mathematical structures used to model pairwise relations between objects. Despite  its simple structures, graphs have applications in various areas like computer science, physics, biology and sociology. The main focus of this work is to continue the study of the coloring and detecting problems in the setting of graph classes closed under taking induced subgraphs (which we call hereditary graph classes).

The first class we consider is ISK4-free graphs - the graphs that do not contain any subdivision of K4 as an induced subgraph. We prove that the chromatic number of this class is bounded by 24, a big improvement compared to the best-known bound. We also give a much better bound in the triangle-free case. Furthermore, we prove that there exists an O(n9) algorithm for detecting this class, which answers a question by Chudnovsky et al. and Lévêque et al.

The second class we study is even-hole-free graphs with no star cutset. This was motivated by the use of decomposition technique in solving some optimization problems. We prove the optimal χ-bounding function for this class and also show that it has bounded rank-width, which implies the existence of a polynomial-time coloring algorithm.

Finally, the connected greedy coloring in claw-free graphs is considered. A natural way to color a graph is to have an order of its vertices and assign for each vertex the first available color. A lot of researches have been done for general orders. However, we know very little about the characterization of good graphs with respect to connected orders. A graph G is good if for every connected induced subgraph H of G, every connected order gives H an optimal coloring.  We give the complete characterization of good claw-free graphs in terms of minimal forbidden induced subgraphs. This also implies a polynomial-time recognition algorithm for this class.