Chromatic number of $P_5$-free graphs: $\chi$-bounding functions

Ingo Schiermeyer
Technische Universität Bergakademie Freiberg

PDF

Minisymposium: VERTEX COLOURINGS AND FORBIDDEN SUBGRAPHS

Content: In this talk we study the chromatic number of $P_5$-free graphs. Gy\'arfas has shown \medskip \noindent{\bf{Theorem}} Let $G$ be a $P_k$-free graph for $k \geq 4$ with clique number $\omega(G) \geq 2.$ Then $\chi(G) \leq (k-1)^{\omega(G)-1}.$ \medskip and has posed the following question: \medskip \noindent{\bf{Question}} Is there a polynomial ($\chi$-bounding) function $f_k$ for $k \geq 5$ such that every $P_k$-free graph $G$ satisfies $\chi(G) \leq f_k(\omega(G))?$ \medskip We will show that there is a polynomial $\chi$-bounding function for several subclasses of $P_5$-free graphs. Our main result is the following. \medskip \noindent{\bf{Theorem}} Let $G$ be a connected $P_5$-free graph of order $n$ and clique number $\omega(G).$ If $G$ is \\ (i) $Claw$-free or (ii) $Paw$-free or (iii) $Diamond$-free or (iv) $Dart$-free or (v) $Gem^+$-free or (vi) $Cricket$-free, \\ then $\chi(G) \leq \omega^2(G).$ \medskip Here $Gem^+$ denotes the graph $(K_1 + (K_1 \cup P_4)).$

Back to all abstracts