Progress on χ-binding functions for P5-free graphs

by Ingo Schiermeyer

Abstract:

A graph $G$ with clique number $\omega(G)$ and chromatic number $\chi(G)$ is perfect if $\chi(H)=\omega(H)$ for every induced subgraph $H$ of $G$ . A family $\cal{G}$ of graphs is called $\chi$ -bounded with binding function $f$ if $\chi(G') \leq f(\omega(G'))$ holds whenever $G \in \cal{G}$ and $G'$ is an induced subgraph of $G$ .

It is an open problem whether the class of $P_5$ -free graphs has a polynomial $\chi$ -binding function. In this talk we will present a survey on polynomial $\chi$ -binding functions for several classes of $(P_5, H)$ -free graphs.

References

[1] C.Brause, B. Randerath, I. Schiermeyer, and E. Vumar, On the chromatic number of 2K2-free graphs, Discrete Applied Mathematics 253 (2019) 14–24.

[2] C. Brause, P. Holub, A. Kabela, Z. Ryjáček, I. Schiermeyer, and P. Vrána, On forbidden induced subgraphs for $K_{1,3}$ -free perfect graphs, Discrete Mathematics 342 (6) (2019) 1602–1608.

[3] I. Schiermeyer and B. Randerath, Polynomial $\chi$ -Binding Functions and Forbidden Induced Subgraphs: A Survey, Graphs and Combinatorics 35 (1) (2019) 1–31.

Event Timeslots (1)

Friday
4:00 pm - 4:25 pm
Ingo Schiermeyer