Polynomial $\chi$-Binding Functions and Forbidden Induced Subgraphs: A Survey

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 ${\mathcal {G}}$ of graphs is called $\chi$-bounded with binding function f if $\chi (G') \le f(\omega (G'))$ holds whenever $G \in {\mathcal {G}}$ and $G'$ is an induced subgraph of G. In this paper we will present a survey on polynomial $\chi$-binding functions. Especially we will address perfect graphs, hereditary graphs satisfying the Vizing bound ($\chi \le \omega +1$), graphs having linear $\chi$-binding functions and graphs having non-linear polynomial $\chi$-binding functions. Thereby we also survey polynomial $\chi$-binding functions for several graph classes defined in terms of forbidden induced subgraphs, among them $2K_2$-free graphs, $P_k$-free graphs, claw-free graphs, and ${ diamond}$-free graphs.

Families of$\chi$-bound graphs are natural candidates for polynomial approximation algorithms for the vertex coloring problem. (András Gyárfás [42])

1 Introduction and Motivation

We consider finite, simple, and undirected graphs, and use standard terminology and notation. Let G be a graph. An induced subgraph of G is a graph H such that $V(H) \subseteq V(G),$ and $uv \in E(H)$ if and only if $uv \in E(G)$ for all $u,v \in V(H).$ Given graphs G and F we say that GcontainsF if F is isomorphic to an induced subgraph of G. A hole in a graph is an induced cycle of length at least four, and an ${ antihole}$ is an induced subgraph whose complement is a ${ hole}$ in the complementary graph. We say that a graph G is F-free, if it does not contain F. For a fixed graph F let ${{\mathcal {G}}}(F)$ denote the family of graphs which are F-free. A family of graphs, where every induced subgraph of a graph is likewise a member of the family of graphs, is called hereditary. Obviously every family of graphs defined in terms of forbidden induced subgraphs is hereditary. For two graphs G and H, we denote by $G\cup H$ the disjoint union and by $G + H$ the join of G and H,  respectively.

A graph G is called k-colourable, if its vertices can be coloured with k colours so that adjacent vertices receive distinct colours. The smallest integer k such that a given graph G is k-colourable is called its chromatic number, denoted by $\chi (G).$ It is well-known that $\omega (G) \le \chi (G) \le \varDelta (G)+1$ for any graph G,  where $\omega (G)$ denotes its clique number and $\varDelta (G)$ its maximum degree.

After explaining some basic terms and notations we now introduce and motivate this survey after describing the history of this research field briefly. In general as shown by Erdős the gap between the clique number $\omega$ and the chromatic number $\chi$ of a graph can be arbitrarily large. This is a classical result in chromatic graph theory.

Theorem 1

(Erdős [34]) For any positive integers $k,l \ge 3$, there exists a graph G with girth $g(G) \ge l$ and chromatic number $\chi (G) \ge k.$

Of very special interest is the hereditary family of graphs attaining equality for the clique number $\omega$ and the chromatic number $\chi$ of its members. A graph G is perfect if $\chi (H)=\omega (H)$ for every induced subgraph H of G.

1.1 Perfect Graphs: $\chi$-Binding Function $f(\omega )=\omega$

Without perfect graphs this survey would not exist. Therefore we present a short introduction to perfect graphs here. Berge [5] contributed for the fascinating class of perfect graphs more than 65 years ago two inspiring conjectures: the perfect graph conjecture proven by Lovász and the strong perfect graph conjecture proven by Chudnovsky, Robertson, Seymour and Thomas.

Theorem 2

(Perfect Graph Theorem [60]) A graph is perfect if and only if its complement is likewise perfect.

Theorem 3

(Strong Perfect Graph Theorem [23]) A graph is perfect if and only if it contains neither an odd cycle of length at least five nor its complement.

A nice family of graphs which are perfect is ${{\mathcal {G}}}(P_4)$ containing graphs without having an induced path on four vertices. These graphs are also known as cographs due to Seinesche who characterised these graphs as follows: G is a cograph, if the complement of every nontrivial connected induced subgraph of G is disconnected. A concise proof of its perfectness can easily be done by the latter property. A non-hereditary subfamily of claw-free graphs is a further example of a family of perfect graphs: every connected $(2K_2, { claw})$-free graph with independence number $\alpha (G) \ge 3$ is perfect as shown by Brause, Holub, Kabela, Ryjáček, Schiermeyer and Vrána [12]¹. A large collection of 120 graph classes, which are all perfect, has been surveyed by Hougardy [47]. For a survey on the attempts to solve the Strong Perfect Graph Conjecture see [70].

Recall the definition of perfect graphs: a graphGis perfect, if for every induced subgraph$G'$ofGthe equality$\chi (G')=\omega (G')$is valid. Due to the lower bound $\omega (G) \le \chi (G)$ for the definition we only need to require that for every induced subgraph $G'$ of G the inequality $\chi (G')\le \omega (G')$ is valid. This variation of the definition of perfect graphs leads to a nice generalization of perfect graphs.

1.2 $\chi$-Binding Functions and $\chi$-Bounded Graphs

A family ${{\mathcal {G}}}$ of graphs is called $\chi$-bounded with $\chi$-binding functionf, if $\chi (G')\le f(\omega (G'))$ holds whenever $G'$ is an induced subgraph of $G\in {{\mathcal {G}}}$. For a smallest$\chi$-binding function of a graph family we use frequently the notation $f^*$. The family of perfect graphs are exactly the graphs having as (smallest) $\chi$-binding function the identity $f(\omega )=\omega$.

The study of $\chi$-binding functions and $\chi$-bounded graphs was initiated by Gyárfás in his landmark paper on problems from the world surrounding perfect graphs [42]. This concept is well defined, since there exists no $\chi$-binding function for general graphs. This easily can be argued for instance with the previously mentioned result of Erdös (Theorem 1) or the following elegant construction of ${ triangle}$-free graphs $G_k$ with chromatic number k (for any k) due to Mycielski [63]. In fact, let $G_1$ be the $K_1$, $G_2$ be the $K_2$, $G_3$ be the $C_5$ and suppose that $G_k$ with $k\ge 3$ has the vertex set $\{ v_1, v_2, \ldots , v_n\}$. Form $G_{k+1}$ by adjoining for each $i=1, 2,\ldots ,n$ a new vertex $w_i$ with $w_i$ being adjacent to every vertex of $N_G(v_i)$ and attaching a new vertex u adjacent to each vertex $w_i$. Note that every graph of the resulting sequence $(G_k)_{k\in {\mathbb {N}}}$ of graphs is ${ triangle}$-free. Moreover, $G_k$ is k-chromatic. The graph $G_4$ is quite often referred to as Grötzsch graph or Mycielski graph (see Fig. 4).

Observe that we can restrict our considerations to connected graphs. More precisely, let $\mathcal {G}$ be a hereditary class of graphs and $\mathcal {G}'$ be the set of connected graphs in $\mathcal {G}$. If f is a $\chi$-binding function for $\mathcal {G'}$, then f is likewise a $\chi$-binding function for $\mathcal {G}$.

1.3 Polynomial $\chi$-Binding Functions and $\chi$-Polybound Graphs

Now we will focus on the subject of this survey. What are polynomial $\chi$-binding functions and $\chi$-polybound graphs ? This is the restriction to those $\chi$-binding functions and $\chi$-bounds which are polynomial, i.e. we study hereditary graph families having a polynomial as $\chi$-binding function and call them $\chi$-polybound. With respect to the quote of Gyárfás in the abstract, we are not only interested in hereditary $\chi$-polybound graph families ${{\mathcal {G}}}$. We also want to study the following problem.

Problem 1

Given a $\chi$-polybound family ${{\mathcal {G}}}$ of graphs with $\chi$-binding function f. Obtain (if possible) a polynomial time algorithm to determine a colouring of $G\in {{\mathcal {G}}}$ requiring at most $f(\omega (G))$ colours. If such an algorithm exists, then we call such a $\chi$-polybound graph family $\chi$-polydet.

In the following we give a nice example in order to get used to the terminology.

1.3.1 $\chi$-Polybound and $\chi$-Polydet in a Nutshell

We now study the family of $(P_4\cup K_1)$-free graphs² and demonstrate that this family of graphs is $\chi$-polybound and $\chi$-polydet. Since $P_4\cup K_1$ is the complement of the ${ gem}$ (see Fig. 1) this graph is also known as co-gem.

Observation 1

Let $\mathcal {G}$ be the family of $(P_4\cup K_1)$-free graphs. Then $\mathcal {G}$ is $\chi$-polybound with $\chi$-binding function $f(\omega )= {\omega +1}\atopwithdelims (){2}$ and $\chi$-polydet.

Consider an arbitrary vertex v of a graph G of $\mathcal {G}$ with $\omega (G)=\omega$. Then $G'=G-N[v]$ is a $P_4$-free graph, thus perfect and due to its cograph structure easily $\omega$-colourable in linear time. One of these colours can be used to colour v of G. It remains to colour the vertices of N(v) of G. These vertices induce a graph $G''$ of $\mathcal {G}$ such that $\omega (G'') \le \omega -1$. By applying recursion we obtain the $\chi$-binding function $f(\omega )= {\omega +1}\atopwithdelims (){2}$. Without loss of generality we can assume that our considered graph G with n vertices satisfies $\omega (G)=\omega \le \sqrt{2n}$. Otherwise colouring each vertex with a different colour would improve a ${\omega +1}\atopwithdelims (){2}$-colouring of G. Furthermore the branch of a recursion is settled as soon as a neighbourhood of a vertex in consideration induces at least two components. The intrinsic case is the one recursively generating a sequence of connected graphs induced by the neighbourhood of the vertices in consideration. Since cographs can be coloured in linear time a coarse estimate yields a $O(n^{3/2})$-time algorithm in order to determine a ${ min} \{ n,{\omega +1}\atopwithdelims (){2} \}$-colouring of G. Thus $\mathcal {G}$ is $\chi$-polydet.³

Fig. 1

${ house}$, $C_4$, ${ diamond},$ and ${ gem}$

Fig. 2

${ claw}$, ${ paw}$, ${ hammer}$, and ${ butterfly}$ (${ windmill}\ W_3^2$)

Fig. 3

${ dart}$, ${ cricket}$ and ${ gem}^+({ parachute})$

Fig. 4

Mycielski/Grötzsch graph $G_4$

1.4 Special Graphs

In this subsection we summarize special graphs used in this survey. We use the notation $P_k$ in order to denote a path having k vertices. Let $K_{1,s}$ denote the ${ star}$ with s branches. The special case $K_{1,3}$ is called a ${ claw}$. Furthermore $S_{i_1,i_2,\ldots ,i_s}$ is the notation of a star with s branches subdivided $i_1-1,i_2-1,\ldots ,i_s-1$ times, respectively. A $r{ -wheel}$ is the join of a cycle of length r and a vertex, i.e. $K_1+C_r$. Let us call 5-ring any graph whose vertex-set can be partitioned into five non-empty independent sets $I_1,\ldots ,I_5$ such that for each j with subscripts modulo 5 the set $I_{j-1}\cup I_j\cup I_{j+1}$ induces a complete bipartite graph. A ${ split graph}$ is a graph G such that V(G) can be partitioned into two sets $S_1$ and $S_2$ for which $S_1$ induces a complete graph and $S_2$ is an independent set in G. A ${ multisplit graph}$ is a graph G such that V(G) can be partitioned into two sets $S_1$ and $S_2$ for which $S_1$ induces a complete multipartite graph and $S_2$ is an independent set in G (Figs. 2, 3, 4, 5).

Fig. 5

$K_5-e$, ${ HVN}$, $K_4$ and $K_3$

Fig. 6

${ banner}$, ${ chair}$ or ${ fork}$$(S_{2,1,1})$, and ${ kite}$$(\overline{S_{2,1,1}})$

Fig. 7

$(P_5,K_4)$-free 5-chromatic graph ${ podracer}$

Fig. 8

${ trident}$($S_{2,2,1,1}$), E($S_{2,2,1}$), ${ cross}$($S_{2,1,1,1}$), and H

2 $\chi$-Polybound Graphs with One Forbidden Induced Subgraph

Several subclasses of perfect graphs can be characterised by forbidden induced subgraphs, e. g. $P_4$-free graphs. What choices of forbidden induced subgraphs guarantee that a family of graphs is $\chi$-bounded? Since there are graphs with arbitrarily large chromatic number and girth, at least one forbidden subgraph has to be acyclic. Gyárfás [42] and independently Sumner [77] conjectured that this necessary condition is also a sufficient condition for a $\chi$-bounded family of graphs defined in terms of forbidden induced subgraphs.

Conjecture 1

(Gyárfás–Sumner conjecture [42, 77]) Let T be any tree (or forest). Then there is a function $f_T$ such that every T-free graph G satisfies $\chi (G) \le f_T(\omega (G)).$

Partial solutions to this conjecture and thereby providing examples of $\chi$-bounded graph families defined in terms of one forbidden induced subgraph have been made by Gyárfás, Szemerédi and Tuza [43] if restricted to ${ triangle}$-free graphs for trees of radius two, and Kierstead and Penrice [56] for trees of radius two. Scott [73] proved a topological version of the conjecture: for every tree T and integer s there is g(s, T) such that every graph G with $\chi (G) > g(s, T )$ contains either $K_s$ or an induced copy of a subdivision of T. Kierstead and Zhu [57] proved the conjecture for radius three trees obtained from radius two trees by making exactly one subdivision in every edge adjacent to the root. Chudnovsky, Scott, and Seymour [28] gave a partial solution for two further family of trees generalizing ${ double}$${ brooms}$ and ${ two-legged}$${ caterpillars}$. A ${ two-legged}$${ caterpillar}$ is a tree obtained from a path by adding two vertices, each with one neighbour in the path. A ${ broom}$ is a tree obtained from a star by replacing one of its edges by a path of arbitrary length. A doublebroom is a tree obtained from two disjoint stars by adding a path between the centers of the stars. Scott and Seymour [75] proved the Gyárfás–Sumner conjecture for the family of $(1,\ldots ,1,2, \ldots ,2)$-multibrooms. For $k\ge 1$, let us say a ${ broom}$ of length k is a tree obtained from a k-edge path with ends a, b by adding some number of leaves adjacent to b, and we call a its ${ handle}$. A tree obtained from ${ brooms}$ of lengths $k_1, \ldots ,k_n$ by identifying their ${ handles}$ is a $(k_1,\ldots ,k_n)$-multibroom. The mentioned result of Kierstead and Penrice [56] can be translated in this terminology asserting that every $(1,\ldots ,1)$-multibroom T satisfies the Gyárfás–Sumner conjecture, and Kierstead and Zhu [57] proved the same for $(2, \ldots ,2)$-multibrooms. In [75] a common generalization regarding $(1, \ldots ,1,2, \ldots ,2)$-multibrooms has been established.

If we consider $\chi$-bounded families of graphs defined in terms of only one forbidden induced subgraph T, then we already know that T is acyclic. Moreover, as observed in [69], the following sequence of graphs $(H_i)$ implies a nice observation. Starting with $H_1=\bar{C_7}$, the complement of the 7-cycle, we define $H_{i+1}=\bar{C_7}[H_i]$, the lexicographic product of the graphs $\bar{C_7}$ and $H_i$. Here, the lexicographic product of two graphs G and H is the graph G[H] with vertex set $V(G)\times V(H)$ and with edges joining (u, v) and $(u',v')$ if and only if $uu'$ is an edge of G or $u=u'$ and $vv'$ is an edge of H. Note that $\omega (H_{i+1})=3\omega (H_i)$. Furthermore, in any colouring of $H_{i+1}$ we need for each copy of $H_i$ at least $\chi (H_i)$ different colours. With $\alpha (\bar{C_7})=2$ we then observe that every colour of a colouring of $H_{i+1}$ appears in at most two different copies of $H_i$. Hence, $H_i$ has the order $n(H_i)=7^i$, independence number $\alpha (H_i)=2^i$ and clique number $\omega (H_i)=3^i$. Therefore, its chromatic number $\chi (H_i)$ is at least $(7/2)^i=(7/6)^i \omega (H_i)$. Furthermore, if a member of the sequence $(H_i)$ contains an acyclic induced subgraph T, then T has to be a subgraph of the path $P_4$. Hence, we observed the following result:

Observation 2

[69] Let ${{\mathcal {G}}}$ be a $\chi$-bounded family of graphs defined in terms of only one forbidden induced subgraph T. Then T is acyclic. Furthermore, if $T\subset P_4$ then ${{\mathcal {G}}}$ has the (smallest) $\chi$-binding function $f^*(\omega )=\omega$, or otherwise there exists no linear $\chi$-binding function f for ${{\mathcal {G}}}$.

2.1 Claw-Free Graphs and $\chi$-Binding Functions

In 1981 Sumner [77] observed that the class of ${ claw}$-free graphs is $\chi$-bounded with $\chi$-binding function $f(\omega )=R(3,\omega )$. Here R(p, q) is the well known Ramsey number. Since the ratio of the order and the independence number of a graph provides a well-known lower bound for its chromatic number and every graph with an independence number of at most two is obviously also a claw-free graph, it is not difficult to observe that for every $\chi$-binding function f of the class of claw-free graphs we have $f(\omega )\ge \frac{R(3,\omega +1 )}{2}$ (cf. [42]). Consequently, by the dependency on the Ramsey number and Kims famous result [58], that the Ramsey number R(3, q) has order of magnitude $q^2/\log q$, the smallest $\chi$-binding function $f_{{ claw}}^*$ has also this magnitude. Combining these results implies the following observation.

Observation 3

[42, 58, 77] There exists no linear $\chi$-binding function f for the class of claw-free graphs. More precisely, for the family of claw-free graphs the smallest $\chi$-binding function $f_{{ claw}}^*$ satisfies $f_{{ claw}}^*(\omega )\in O(\frac{\omega ^2}{\log \omega })$.

Chudnovsky and Seymour [21] established for the non-hereditary subfamily of ${ claw}$-free graphs G with $\alpha (G) \ge 3$ the linear bound $2\omega (G)$ for $\chi$.

The next result of Gyárfás [42] shows that the magnitude of the smallest $\chi$-binding function for the class of $K_{1,n}$-free graphs is likewise strongly related to Ramsey numbers.

Theorem 4

[42] The family of $K_{1,n}$-free graphs is $\chi$-bounded and its smallest $\chi$-binding function $f^*$ satisfies $\frac{R(n,\omega +1)-1}{n-1}\le f^*(\omega )\le R(n,\omega )$.

A supergraph of the ${ claw}$ is a ${ chair}$ (see Fig. 6). In [66] it has been shown that $f_{{ chair}}^*(2)=3$ and $f_{{ chair}}^*(3)=4$, if $f_{{ chair}}^*$ is the smallest $\chi$-binding function for the class of ${ chair}$-free graphs. Moreover, we expect that $f_{{ chair}}^*(\omega )=f_{{ claw}}^*(\omega )$. Since Kierstead and Penrice [56] confirmed the Gyárfás–Sumner conjecture for trees of radius two, there exists a $\chi$-binding function for the class of ${ chair}$-free graphs.

Question 1

Does there exist a polynomial $\chi$-binding function for the family of ${ chair}$-free graphs ?

2.2 $\chi$-Binding Functions of Graphs Without Long Induced Paths $P_k$

For the family of $P_k$-free graphs, where $P_k$ is a path on k vertices, an exponential $\chi$-binding function is known.

Theorem 5

[42] The family of $P_k$-free graphs is $\chi$-bounded and its smallest $\chi$-binding function $f^*_k$ satisfies

$$\begin{aligned} \frac{R(\lceil k/2\rceil ,\omega +1)-1}{\lceil k/2\rceil -1}\le f^*_k(\omega )\le (k-1)^{\omega -1}. \end{aligned}$$

The idea of the proof of Theorem 5 in order to establish the upper bound will be illustrated for the special case of triangle-free graphs. Thereby we slightly improve the upper bound.

Corollary 1

[69] Let G be a ${ triangle}$-free and $P_k$-free graph. Then

$$\begin{aligned} \chi (G)\le k-2,\quad \text {i.e. } \ f^*_k(2)\le k-2. \end{aligned}$$

Proof

Assume to the contrary that there exists a triangle-free and $P_k$-free graph $G_1$ with $\chi (G_1)\ge k-1$. Say, $G_1$ is connected. Let $v_1$ be a vertex of $G_1$. Since all neighbours of $v_1$ form an independent set of $G_1$, we deduce that the induced subgraph $G_1-N_{G_1}[v_1]$ contains a component $G_2$ with $\chi (G_2)\ge k-2$. Since $G_1$ is connected there exists a neighbour $v_2$ of $v_1$ such that $v_2$ is also adjacent to at least one vertex of $G_2$. Now proceed iteratively until we receive a sequence of nested graphs $(G_i)_{i\in \{ 1,\ldots ,k-3\}}$. Observe that the vertex set $\{ v_1,v_2,\ldots ,v_{k-3}\}$ induces a path $P_{k-3}$ and $\chi (G_{k-3})\ge 3$. Because $G_{k-3}$ is ${ triangle}$-free and not bipartite there exists an induced odd ${ hole}$C containing at least five vertices. Now it is not very difficult to extend the path $P_{k-3}$ along C in order to produce an induced path of $G_1$ containing at least k vertices, a contradiction. $\square$

For $k=5$ the $C_5$ is a ${ triangle}$-free and $P_5$-free graph with $\chi (C_5)=3$. For $k=6$ the Mycielski/Grötzsch graph $G_4$ is a ${ triangle}$-free and $P_6$-free graph with $\chi (G_4)=4.$ Hence this upper bound is sharp for $k=4,5,6$.

Question 2

Does there exist a ${ triangle}$-free and $P_7$-free graph G with $\chi (G)=5$ or even a sequence of graphs attaining the bound of the last corollary for all $k \ge 7$?

The upper bounds in Theorem 5 and Corollary 1 has been improved by Gravier et al. [41].

Theorem 6

[41] Let G be a $P_k$-free graph for $k \ge 4$ with clique number $\omega (G) \ge 2.$ Then

$$\begin{aligned} f_k(\omega ) \le (k-2)^{\omega (G)-1}. \end{aligned}$$

For short paths more research has taken place. Recall that $P_4$-free graphs are perfect. The currently best known upper bound for $P_5$-free graphs is due to Esperet, Lemoine, Maffray, and Morel [35].

Theorem 7

[35] Let G be a $P_5$-free graph with $\omega (G) \ge 3.$ Then $\chi (G) \le 5 \cdot 3^{\omega (G)-3}.$

The 5-chromatic, $P_5$-free and $K_4$-free ${ podracer}$ (cf. [66] or Fig. 7) is an example attaining the upper bound of the latter result. If $f^*_{P_5}$ denotes the smallest $\chi$-binding function for $P_5$-free graphs, then we have $f^*_{P_5}(3)=5$ and by Observation 4 that $f^*_{P_5}(2)=3$. One may wonder whether the exponential bound of the last theorem can be improved. In particular:

Question 3

Does there exist polynomial ($\chi$-binding) functions $f_k$ for $k \ge 5$ such that every $P_k$-free graph G satisfies $\chi (G) \le f_k(\omega (G))?$

If there would be a polynomial ($\chi$-binding) function $f_k$ for some $k \ge 5,$ then it would imply the Erdős-Hajnal conjecture for $P_k$-free graphs. The Erdős-Hajnal conjecture states that for every graph H, there exists a constant $\delta (H) > 0$ such that every graph G with no induced subgraph isomorphic to H has either a clique or a stable set of size at least $|V(G)|^{\delta (H)}.$ However, the Erdős-Hajnal conjecture is still open for $P_k$-free graphs for all $k \ge 5$ (cf. [20] for a survey).

The currently best known upper bound for $P_6$-free graphs is due to Gravier et al [41].

Theorem 8

[41] Let G be a $P_6$-free graph with clique number $\omega (G) \ge 3.$ Then $\chi (G) \le 4 \cdot 3^{\omega (G)-1}.$

2.3 $\chi$-Binding Functions of Graphs Without Induced Linear Forests with Emphasis on $2K_2$-Free Graphs

Some further nice examples of graph families having polynomial $\chi$-binding function can be found whilst examining $2K_2$-free graphs or F-free graphs with F being a linear forest, i.e. a forest only containing paths as components. Research on the chromatic number of $2K_2$-free graphs was motivated by the following problem posed by Gyárfás.

Problem 2

[42] What is the order of magnitude of the smallest $\chi$-binding function for ${{\mathcal {G}}}(2K_2)?$

One of the earliest results is due to Wagon, who has considered graphs without induced matchings. For the class of $mK_2$-free graphs, Wagon [81] provides an $O(\omega ^{2(p-1)})$$\chi$-binding function. Let us restate the special case for $p =2$:

Theorem 9

[81] Let G be a $2K_2$-free graph, then $\chi (G) \le {\omega (G)+1 \atopwithdelims ()2}.$

Thus the family of $2K_2$-free graphs is $\chi$-polybound with a quadratic $\chi$-binding function. Since Wagons proof of this bound likewise launches an efficient algorithm to colour a $2K_2$-free graph G using ${\omega (G)+1 \atopwithdelims ()2}$ colours, this graph family is $\chi$-polydet as well. The best known lower bound is $\frac{R(C_4, K_{\omega + 1})-1}{3},$ where $R(C_4, K_{\omega + 1})$ denotes the Ramsey number, i.e. the smallest n such that every graph on n vertices contains either a clique of size $\omega + 1$ or the complement of the graph contains a $C_4$ (a cycle on four vertices). The above lower bound is non-linear because $R(C_4, K_t)$ is known to be at least $t^{1+\epsilon }$ for some $\epsilon > 0$ as proved by Chung in [30].

Concerning the smallest $\chi$-binding function $f^*$ for ${{\mathcal {G}}}(2K_2)$ it has been shown that $f^*(2)=3$ and $f^*(3)=4.$ Clearly, $f^*(2)=3$ follows by Theorem 9 and the fact that the $C_5$ is 3-chromatic. As communicated to Gyárfás (cf. [42]), Erdős offered $20\$$ to decide whether $f^*(3)=4$, and the prize went to Nagy and Szentmiklóssy who proved $f^*(3)=4$. Since the 5-wheel, the join of a 5-hole and a vertex, is 4-chromatic, $K_4$-free and $2K_2$-free, we easily obtain $f^*(3) \ge 4$. It seems that Nagy and Szentmiklóssy never published their proof of $f^*(3)=4$. Very recently a long proof of the result $f^*(3) = 4$ has been published by Gasper and Huang [39]. For proving the result they made use of the result by Chudnovsky, Robertson, Seymour and Thomas [24] that (odd-hole, $K_4)$-free graphs are 4-colourable. During the BIRS workshop “New trends in graph colouring” Yuditsky [82] by using $f^*(3) =4$ mentioned an improvement of the upper bound of Theorem 9 by 2 for all values $\omega \ge 3.$ This improves a recently obtained result of Karthick and Mishra [53]. They were able to show $f^*(4) \le 9$.

Theorem 9 admits a nice generalization as follows (cf. [72]).

Theorem 10

[72] Let H be a graph such that ${{\mathcal {G}}}(H)$ has an $O(\omega ^t)$$\chi$-binding function for some $t \ge 1$, and let G be a $K_2\cup H$-free graph with clique number $\omega (G).$ Then G has an $O(\omega ^{2+t})$$\chi$-binding function.

For the class of $pK_2$-free graphs, we already mentioned in case of $p=2$ Wagons result.

Theorem 11

[81] The family ${{\mathcal {G}}}(pK_2)$ has an $O(\omega ^{2p-2})$$\chi$-binding function for all $p \ge 1.$

For ${ triangle}$-free graphs, Brandt [10] has shown the following improved upper bound.

Theorem 12

[10] Let G be a $(pK_2, K_3)$-free graph with $p \ge 3.$ Then $\chi (G) \le 2p-2.$

Note that the statement of Theorem 11 can be made more precise as follows. In [81] a $\chi$-binding function $f_p(\omega )$ for the class of $pK_2$-free graphs was defined by $f_1(\omega )=1, f_{p+1}(\omega ) = {\omega \atopwithdelims ()2}f_p(\omega ) + \omega .$ From this one can deduce that $f_p(\omega ) \le (\omega + 1)\frac{\omega ^{2p-3}}{2^{p-1}}$ for all $p \ge 1.$ Like Theorem 10 for Theorem 9, Theorem 11 has the following counterpart.

Theorem 13

[72] Let H be a graph such that ${{\mathcal {G}}}(H)$ has an $O(\omega ^t)$$\chi$-binding function for some $t \ge 1$, and let G be a $pK_2 \cup H$-free graph with clique number $\omega (G).$ Then G has an $O(\omega ^{2p-2+t})$$\chi$-binding function.

In Gyárfás’ study of the smallest $\chi$-binding function $f^*_T$ for the class of T-free graphs, where T is a forest with four vertices, there are three subcases left over. As shown in [42] $f^*_{P_3\cup K_1}$ behaves asymptotically like $\frac{R(3,\omega +1)}{2}$. Thus, analogously to the case of claw-free graphs, the magnitude of $f^*_{P_3\cup K_1}$ is $O(\frac{\omega ^2}{\log \omega })$. The graph $\overline{P_3\cup K_1}$ is the ${ paw}$. Note that by a result of Olariu [64] on the class of paw-free graphs, asserting that every paw-free graph is either triangle-free or a complete multipartite graph, it is not difficult to obtain that $f^*_{P_3\cup K_1}(\omega )=f^*_{3K_1}(\omega )$. Here, $f^*_{3K_1}$ is the smallest $\chi$-binding function for the class of $3K_1$-free graphs. Also in [42] the asymptotic behaviour $\frac{R(4,\omega +1)}{3}$ of $f^*_{4K_1}$ is mentioned. Finally, Gyárfás established $\frac{R(3,\omega +1)-1}{2}\le f^*_{K_2\cup 2K_1}(\omega )\le {\omega +1 \atopwithdelims ()2}+\omega -1$. With a slight modification of the proof of Theorem 14 it is not very difficult to establish the upper bound ${\omega +1 \atopwithdelims ()2}$ for $f^*_{K_2\cup 2K_1}$.

Now we turn our attention to the smallest $\chi$-binding function $f^*_T$ of the family of T-free graphs, where T is a forest of order 5. In the last subsection we already addressed the case $T=P_5$ with $f^*_{P_5}(2)=3$, $f^*_{P_5}(3)=5$ and by Theorem 7 the bound $f^*_{P_5}(\omega )\le 5 \cdot 3^{\omega (G)-3}$. The next result just recalls parts of Observation 1 and the trivial fact that the family of $P_4\cup K_1$-free graphs contain all $P_3\cup K_1$-free graphs.

Theorem 14

The family of $P_4\cup K_1$-free graphs is $\chi$-bounded and its smallest $\chi$-binding function $f^*_{P_4\cup K_1}$ satisfies $\frac{R(3,\omega +1 )}{2}\le f^*_{P_4\cup K_1}(\omega )\le {\omega +1\atopwithdelims ()2}$.

Analogously one can obtain the following results:

• (i) $\frac{R(5,\omega +1)-1}{4}\le f^*_{5K_1}(\omega )\le R(5,\omega )$;

• (ii) $\frac{R(3,\omega +1 )}{2}\le f^*_{K_2\cup 3K_1}(\omega )\le {\omega +2\atopwithdelims ()3}$;

• (iii) $O(\omega ^{1+\epsilon })\le R(4,\omega +1 )\le f^*_{2K_2\cup K_1}(\omega )\le {\omega +2\atopwithdelims ()3}$ for some $\epsilon >0$;

• (iv) $O(\frac{\omega ^2}{\log \omega })=\frac{R(3,\omega +1 )}{2}\le f^*_{K_1\cup K_{1,3}}(\omega )\le {\omega +2\atopwithdelims ()3}$.

The remaining open case for an acyclic graph of order 5, the $P_3\cup K_2$, has recently been settled by Bharathi and Choudom.

Theorem 15

[6] If G is a $(P_3\cup K_2)$-free graph, then $\chi (G) \le {\omega +2\atopwithdelims ()3}.$

The proof of this result is strong enough to prove a slight extension.

Theorem 16

[6] If G is a $(P_4\cup K_2)$-free graph, then $\chi (G) \le {\omega +2\atopwithdelims ()3}.$

In subsequent sections we will focus on further families of graphs having non-linear $\chi$-binding functions.

3 The Vizing Bound: $\chi$-Binding Function $f(\omega )=\omega +1$

The problem of colouring the edges of a graph G is equivalent to the problem of colouring the vertices of its line graph L(G). Here a line graph L(G) of a graph G is having the edges of G as its vertices, and two distinct edges of G are adjacent in L(G) if they are adjacent in G. Clearly, every edge colouring of a graph G is a vertex colouring of L(G) and vice-versa. Moreover, the maximum degree $\varDelta (G)$ of a graph G,  which is non-isomorphic to a triangle, is equal to the clique number $\omega (L(G)).$ Therefore, Vizing’s Theorem asserting that every graph G can be edge coloured with $\varDelta (G) +1$ colours can be reformulated in the language of line graphs. Namely, every graph G satisfies the inequality $\chi (L(G)) \le \omega (L(G))+1$. Because of Vizings’s result line graphs satisfy this bound $\omega + 1$ for the chromatic number in a quite natural way. Therefore, this special upper bound for the chromatic number was called the Vizing bound in [66]. For more details on the Vizing bound including the characterisation of line graphs in terms of nine forbidden induced subgraphs due to Beineke see [4, 69].

More than 30 years ago Kierstead proved the following theorem, which was conjectured by Javdekar [48].

Theorem 17

(Kierstead [55]) If G is a $(K_{1,3}, K_5-e)$-free graph, then $\chi (G) \le \omega (G) + 1.$

This result forms a partial solution to the following problem.

Problem 3

Find all pairs (A, B) of connected forbidden induced subgraphs such that every (A, B)-free graph satisfies the Vizing bound for the chromatic number.

Remark 1

This problem has many variations to be generalized:

• Find all pairs of forbidden induced subgraphs which imply the Vizing bound.

• Find all k-tuples with $k>2$ of (connected) forbidden induced subgraphs which imply the Vizing bound for the chromatic number. It is noteworthy that the corresponding problem for perfect graphs, i.e. graphs attaining the $\chi$-binding function $f(\omega )=\omega ,$ is very tractable.⁴

• Solve the latter problems by relaxing the Vizing bound slightly,i.e.study graph classes satisfying instead of the Vizing bound the $\chi$-bound $f(\omega (G) ) = \omega (G) +k$ with $k\in {\mathbb {N}}^+$.

A pair (A, B) of connected forbidden induced subgraphs, which imply the Vizing bound for the chromatic number, such that neither forbidding A nor forbidding B is superfluous, is briefly called a good Vizing-pair. Moreover, a good Vizing-pair is saturated, if for every good Vizing-pair $(A',B')$ with $A \subset A'$ and $B \subset B'$ we have $A \cong A'$ and $B \cong B'.$ Based on Erdős’ already cited famous result and a number of certain graphs G with chromatic number $\omega (G) = \omega +2$ it is not difficult to obtain the following result (cf. [66, 69]).

Theorem 18

[66] If (A, B) is a good Vizing-pair, then A has to be a tree with $A \not \subset P_4$ and $B \in \{K_5-e, HVN, K_4, K_3, { diamond}\}$ (see Fig. 5).

Here ${ HVN}$ is the graph $((K_1 \cup K_2)+K_2)$ containing the complete graph on five vertices minus two edges incident to the same vertex. This graph is called in German Haus vom Nikolaus (see Fig. 5).

Theorem 19

[66] Let A be a connected graph such that every A-free graph G with $\omega (G) \le 3$ satisfies $\chi (G) \le \omega (G) +1 \le 4.$ Then A is an induced subgraph of the chair.

The next result extends Kierstead’s generalization of Vizing’s Theorem. The proof is very tedious and was carried out in [66].

Theorem 20

(Randerath, [66]) Let B be an induced subgraph of the ${ HVN}$ or the $K_5-e$ and G be a B-free and chair-free graph, then $\chi (G) \le \omega (G) +1$ (see Fig. 6).

A subproblem is to determine all pairs (A, B) of connected graphs such that a graph G is 3-colourable, if G does not admit either A or B as an induced subgraph.

Theorem 21

[66, 67] Let (A, B) be a saturated pair of connected forbidden induced subgraphs implying 3-colourability. Then $A \in \{K_3, K_4\}$ and $B \subset B' \in \{P_4, H, { trident}\}.$ Moreover, if $A \cong K_4,$ then $B \cong P_4.$ In the case that $A \cong K_3,$ then $B \cong H$ or B is an induced subgraph of the ${ trident}$ (see Fig. 8).

Together with the following theorem an almost complete characterisation of all saturated pairs (A, B) implying 3-colourability was achieved in [66, 67].

Theorem 22

[66, 67] The following list of good pairs (A, B) of connected forbidden induced subgraphs imply 3-colourability:

• 1. $(K_4,P_4)$, i.e. with no $K_4$ and no induced path of order four;

• 2. $(K_3,H)$, where H is a six-vertex graph drawn like the capital letter H;

• 3. $(K_3,E)$, where E is a six-vertex graph drawn like the capital letter E;

• 4. $(K_3,{ cross})$, where the ${ cross}$ is a $K_{1,4}$ with exactly one edge subdivided once.

Conjecture 2

(Randerath, [66, 67]) If G is a ${ triangle}$-free and ${ trident}$-free graph, then $\chi (G) \le \omega (G) +1.$

Here ${ trident}$ denotes a seven-vertex graph drawn like a trident, which is a star with four branches with two edges subdivided (see Fig. 8). A partial solution to this conjecture has been made by Fan, Xu, Ye, Yu.

Theorem 23

[36] If G be a ${ triangle}$-, $C_5$- and ${ trident}$-free graph, then $\chi (G) \le \omega (G) +1.$

Theorem 24

[66] Let G be a ${ triangle}$-free graph. If G is H- or E-free, then $\chi (G) \le \omega (G) +1.$

3.1 Paw-Free Graphs and the Vizing Bound

A superclass of the triangle-free graphs is the class of ${ paw}$-free graphs. The ${ paw}$ is a ${ triangle}$ with an attached endvertex. A structural characterisation of ${ paw}$-free graphs is due to Olariu [64]. He discovered that the connected, ${ paw}$-free and non-${ triangle}$-free graphs are exactly the complete multipartite graphs with at least three partite sets. Roughly speaking, the “gap” between the class of ${ triangle}$-free graphs and the class of ${ paw}$-free graphs is not very large. Note that every complete multipartite graph G is $\omega (G)$-colourable. Hence, as observed in [66] the results concerning ${ triangle}$-free graphs can be transformed to those concerning ${ paw}$-free graphs, i.e.

$$\begin{aligned} (paw,B)\text { is a good pair if and only if }(K_3,B)\text { is a good pair}. \end{aligned}$$

Notice that therefore all good pairs (A, B) with $A=K_3$ that have been determined are not saturated pairs. Thus, we have the following set $({ paw},B)_{\omega +1}$ containing all saturated pairs (A, B) with $A={ paw}$:

$$\begin{aligned} (paw,B)_{\omega +1}=(K_3,B)_3 . \end{aligned}$$

Note that, if the previous ${ trident}$-conjecture is true, we have

$$\begin{aligned} (paw,B)_{\omega +1}=\{ (paw,H); (paw,trident) \} \end{aligned}$$

and, if the last ${ trident}$-conjecture is not true, we have

$$\begin{aligned} (paw,B)_3=\{ (paw,H); (paw,cross); (paw,E)\} . \end{aligned}$$

Corollary 2

[66] Let G be a ${ paw}$-free graph. If G is H-free, ${ cross}$-free or E-free, then $\chi (G) \le \omega (G) +1.$

Since $2K_2$ is an induced subgraph of the $P_5$ and the $P_5$ is an induced subgraph of the E,  we have another corollary of Brause et al. by using the following observation.

Observation 4

[66, 77] Let G be a triangle-free and $P_5$-free graph, then $\chi (G) \le \omega (G)+1\le 3$. Moreover, if G is connected, then equality holds if and only if G is a 5-ring.

Corollary 3

[13] If G is a connected $(2K_2, { paw})$-free graph, then G is perfect or G is a 5-ring. In the later case, $\omega (G) = 2$ and $\chi (G) = 3.$

A similar result is due to Blázsik et al. .

Theorem 25

[7] If G is a $(2K_2, C_4)$-free graph with clique number $\omega (G),$ then $\chi (G) \le \omega (G) + 1.$ Furthermore, equality holds if and only if G is not a split graph.

3.2 Diamond-Free Graphs and the Vizing Bound

We start this subsection with the proof of a known result as given in [66] in order to get used to terminology and methods.

Theorem 26

[17, 50, 66] If G is a $(P_5, { diamond})$-free graph, then $\chi (G) \le \omega (G) + 1.$

Before showing that every ${ diamond}$-free and $P_5$-free graph G is $(\omega (G)+1)$-colourable, we need the characterisation of 3-chromatic ${ triangle}$-free and $P_5$-free graphs of Observation 4. The major tool in the proof is a structural characterisation of $P_5$-free graphs in terms of dominating induced subgraphs by Bascó and Tuza [3], asserting that a connected graph G is $P_5$-free if and only if each connected induced subgraph has a dominating clique or a dominating 5-${ hole}$C.

Proof

Assume that there exists a $P_5$-free and ${ diamond}$-free graph G with $\chi (G)=\omega (G)+2$ and suppose that G has a minimum number of vertices. In the following we abbreviate $\omega (G)$ by $\omega$, $\chi (G)$ by $\chi$ and the minimum degree $\delta (G)$ by $\delta$. Obviously, G is $(\omega +2)$-vertex-critical and therefore $\delta \ge \omega +1$. Since G is a minimal order counterexample, G is connected. With the last observation we immediately deduce $\omega \ge 3$. With the characterisation of Bascó and Tuza G has a dominating clique Q or a dominating 5-hole C, i.e. $V(G)=N_G[V(Q)]$ or $V(G)=N_G[V(C)]$. Along the two different choices the remaining part is organized as follows.

Case 1 G has a dominating clique Q.

Say Q has to be a maximal clique. Since Q is a dominating maximal clique and G is diamond-free, each vertex of $V(G)-V(Q)$ is adjacent to exactly one vertex of Q. For convenience, let $V(Q)=\{ v_1, v_2,\ldots , v_r\}$ and $I_j=:N_G(v_j)-V(Q)$ for $j\in \{ 1, 2,\ldots , r\}$. With the ${ diamond}$-freeness of G we also deduce that for every $j\in \{ 1, 2,\ldots , r\}$ the graph $G[I_j]$ is $P_3$-free, i.e. each component of $G[I_j]$ is a complete graph (of order at most $\omega -1)$. Thus, since we have $\delta \ge \omega +1$ for every $j_0\in \{ 1, 2,\ldots , r\}$, every vertex $w_{j_0}\in I_{j_0}$ is adjacent to at least two vertices $w'$ and $w''$ of $V(G)-(V(Q)\cup I_{j_0})=\cup _{j\ne j_0}I_j$. Suppose that for every $j\in \{ 1, 2,\ldots , r\}$ the set $I_j$ is independent. Then $I^*_j:=I_j\cup \{ v_{j+1}\}$ for $j\in \{ 1, 2,\ldots , r-1\}$ and $I^*_r:=I_r\cup \{ v_1\}$ form r independent sets of G. Then with $V(G)=\cup _{j=1}^rI^*_j$ and $r{\mathop {=}\limits ^{!}}\omega$ this partition of the vertex set of G represents an $\omega$-colouring of G—a contradiction to $\chi =\omega +2$. Hence, there exist two adjacent vertices $w_1^{(1)}$ and $w_2^{(1)}$ in, say $I_1$. Recall that every vertex of $I_1$ is adjacent to at least two vertices of $\cup _{j=2}^rI_j$. For instance $w_2^{(1)}$ is adjacent to, say $w_1^{(2)}\in I_2$. But then either $\{ v_1, w_1^{(1)}, w_2^{(1)}, w_1^{(2)}\}$ induces a ${ diamond}$ or $\{ w_1^{(1)}, w_2^{(1)}, w_1^{(2)}, v_2, v_3\}$ induces a $P_5$—a final contradiction for the first case.

Case 2 G has a dominating 5-hole C.

Let $C=v_0v_1v_2v_3v_4v_0$ be a dominating 5-hole of G, i.e. $V(G)=N_G[V(C)]$. Note that every vertex w of $V(G)-V(C)=N_G(V(C))-V(C)$ is not adjacent to three or more consecutive C-vertices. Otherwise, if w is adjacent to, say $v_1, v_2$ and $v_3$, then $\{ v_1, v_2, v_3, w\}$ induces a ${ diamond}$—a contradiction. Furthermore, if $w\in V(G)-V(C)$ is adjacent to exactly one vertex of C or to exactly two adjacent C-vertices, then it is not very difficult to detect an induced $P_5$. In the following all indices will be taken subscript modulo 5. Hence, we define two different types of sets: $I_j^{(2)}:=\{ w\in N_G(V(C))-V(C)| N_G(w)\cap V(C)=\{ v_j, v_{j+2}\} \}$ for $j\in \{ 0, 1,\ldots , 4\}$ ; $I_j^{(3)}:=\{ w\in N_G(V(C))-V(C)| N_G(w)\cap V(C)=\{ v_{j-1}, v_j, v_{j+2}\} \}$ for $j\in \{ 0, 1,\ldots , 4\}$. Note that $V(G)=\cup _{j=0}^4(\{ v_{j+1}\} \cup I_j^{(2)}\cup I_j^{(3)})$. Furthermore, the diamond-freeness of G forces $|I_j^{(3)}|\le 1$ for every $j\in \{ 0, 1,\ldots , 4\}$ and $I^{(3)}:=\cup _{j=0}^4I_j^{(3)}$ forms an independent set of G. Also $T_j:=\{ v_{j+1}\} \cup I_j^{(2)}\cup I_j^{(3)}$ is an independent set of G for every $j\in \{ 0, 1,\ldots , 4\}$. Therefore, obviously G is 5-colourable. Then with $\chi =\omega +2$ and $\omega \ge 3$ we obtain $\chi =5$ and $\omega =3$. Note that since G is $P_5$-free for every $j\in \{ 0, 1,\ldots , 4\}$, every vertex of the independent set $(\{ v_{j+1}\} \cup I_j^{(2)})$ is adjacent to every vertex of $(\{ v_{j+2}\} \cup I_{j+1}^{(2)})$. Assume that for every $j\in \{ 0, 1,\ldots , 4\}$ every vertex of the independent set $(\{ v_{j+1}\} \cup I_j^{(2)})$ is not adjacent to any vertex of $(\{ v_{j+3}\} \cup I_{j+2}^{(2)})$. Then obviously $G':=G[\cup _{j=0}^4(\{ v_{j+1}\} \cup I_j^{(2)}) ]$ is a $5-ring$. Thus, we then obtain with $\chi (G')=3$ and $G-V(G')=G[I^{(3)}]$ that G is 4-colourable—a contradiction. Hence, the assumption is false and there exists two adjacent vertices, say $w_0\in I_0^{(2)}$ and $w_2\in I_2^{(2)}$. If there exists a vertex $w_1\in I_1^{(2)}$, then $\{ w_0, w_1, v_2, w_2\}$ induces a diamond—a contradiction. Hence, we have $I_1^{(2)}=\emptyset$. Now all sets $T'_j:=T_j$ for $j=\{ 0, 2\}$, $T'_4:=T_4\cup \{ v_2\}$ and $T'_3:=T_3\cup I_1^{(3)}$ are independent in G. Hence, then with $V(G)=T'_0\cup (\cup _{j=2}^4T'_j)$ we deduce that G is 4-colourable—a contradiction. This contradiction finally completes the proof of the result. $\square$

It is noteworthy that although the proof of this result is by contradiction the ideas of the proof can be used to generate an algorithm in order to colour the vertices of a $(P_5,{ diamond})$-free graph G with $\omega (G)+1$ colours efficiently,i.e.the family of $(P_5,{ diamond})$-free graphs is $\chi$-polydet. It is likely for most of the proofs establishing a polynomial $\chi$-binding function for a family of graphs that this family of graphs is likewise $\chi$-polydet.

The following result is a corollary.

Corollary 4

[6] If G is a $(2K_2, { diamond})$-free graph, then $\chi (G) \le \omega (G) + 1.$

By enlarging the ${ diamond}$ to a ${ gem}$ the last corollary has another option to be generalized based on the following theorem by Brause et al. .

Theorem 27

[13] If G is a $(2K_2, { gem})$-free graph with clique number $\omega (G),$ then

• 1. G is perfect or

• 2. G contains an induced $C_5$ and $\chi (G) = \omega (G) \ge 3$ or

• 3. G is a 5-ring

The proof of Theorem 27 admits the following corollary.

Corollary 5

[13] If G is a $(2K_2, { gem})$-free graph, then $\chi (G) \le max\{3,\omega (G)\}.$

Another graph enlarging the ${ diamond}$ is the graph $\overline{P_2 \cup P_3}$. Karthick and Mishra examined the class of $(2K_2, \overline{P_2 \cup P_3})$-free graphs.

Theorem 28

[54] If G is $(2K_2, \overline{P_2 \cup P_3})$-free, then $\chi (G) \le \omega (G) + 1$

Since a $P_5$ is likewise an induced subgraph of the $P_6$ and the E graph, the following result generalizes this subsections initial result on $(P_5, { diamond})$-free graphs.

Theorem 29

[50] Let G be a $(P_6, E, { diamond})$-free graph, then $\chi (G) \le \omega (G)+1.$

4 $\chi$-Polybound Graphs with Linear $\chi$-binding Functions

In this section we study further graph families ${\mathcal {G}}$ having a linear $\chi$-binding function f,i.e.every $G\in {\mathcal {G}}$ satisfies $\chi (G) \le \alpha \omega (G) +\beta$ with $\alpha , \beta \in {\mathbb {R}}$. An intermediate step to extend graph families satisfying the Vizing bound would be the investigation of graph families having $\chi$-binding functions $f(\omega (G) ) = \omega (G) +k$ with $k\in {\mathbb {N}}^+$. A beautiful example of this type of $\chi$-polybound graphs has recently been provided by Cameron, Huang and Merkel thereby improving a result and answering a problem raised by Karthick and Mishra [51].

Theorem 30

[15] Let G be a $(P_6, { diamond})$-free graph, then $\chi (G) \le \omega (G)+3.$

The authors also notice in their work that the bound is attained by the complement of the famous 27-vertex Schläfli graph. Moreover they address in their conclusion the remark that “one can turn the proof into a polynomial-time algorithm for colouring a$(P_6,{ diamond})$-free graphGusing$\omega (G)+3$colours”. Thus the family of $(P_6,{ diamond})$-free graphs is also $\chi$-polydet.

Corollary 6

[51] Let G be a $(P_6, { diamond})$-free graph, then

• 1. $\chi (G) \le 2\omega (G)+5$ for $\omega \ge 4$ and

• 2. $\chi (G) \le 6$ for $\omega \le 3.$

For the subfamily of $(P_3\cup P_2, { diamond})$-free graphs Bharathi and Choudom were able to refine the upper bound.

Theorem 31

[6] If G is a $(P_3\cup P_2, { diamond})$-free, then

• 1. G is perfect if $\chi (G) = \omega (G) \ge 5$ or $\chi (G)\le \omega (G)+1$ if $\omega (G)=4$ or

• 2. $\chi (G)\le \omega (G)+3$ if $\omega (G)=3$ or $\chi (G)\le \omega (G)+2$ if $\omega (G)=2.$

Let us remind on Observation 2 asserting for a $\chi$-bounded family ${{\mathcal {G}}}$ of graphs defined in terms of only one forbidden induced subgraph T, that then T is acyclic and if $T\subset P_4$ then ${{\mathcal {G}}}$ has the (smallest) $\chi$-binding function $f^*(\omega )=\omega$, or otherwise there exists no linear $\chi$-binding function f for ${{\mathcal {G}}}$. So our first examples of this section predict already a necessary condition for a graph family defined in terms of forbidden induced subgraphs to guarantee a linear $\chi$-binding function: The graph family has to be defined by forbidding at least two induced subgraphs.

4.1 $\chi$-Polybound, $(P_k, B)$-free Graphs with Linear $\chi$-Binding Functions

Another contribution of a linear $\chi$-bounded subfamily of $P_6$-free graphs has been given by Karthick and Maffray. The class of $(P_6,C_4)$-free graphs is obviously also $\chi$-polydet, since the authors also present based on a structural characterisation of this class a polynomial-time algorithm to determine the chromatic number $\chi$ for this graph class.

Theorem 32

[51] Let G be a $(P_6, C_4)$-free graph, then $\chi (G) \le \lceil \frac{5\omega (G)}{4}\rceil$.

We will now prove a linear bound for the class of $(P_k, gem)$-free graphs.

Theorem 33

Let G be a $(P_k,{ gem})$-free graph for $k \ge 4$ with clique number $\omega (G) \ge 2.$ Then

$$\begin{aligned} f_k(\omega ) \le (k-2)(\omega (G)-1). \end{aligned}$$

Proof

We prove by induction on $k \ge 4.$ To start the induction, note that $P_4$-free graphs are perfect. Hence

$$\begin{aligned} \chi (G) = \omega (G) \le 2\omega - 2 \end{aligned}$$

for all $\omega \ge 2.$ Suppose now that $(k-2)(\omega - 1)$ is a $\chi$-binding function for all graphs $G' \in {{\mathcal {G}}}(P_k, { gem})$ for some fixed $k \ge 4.$ Let $G \in {{\mathcal {G}}}(P_{k+1}, { gem}).$ Assuming that $\chi (G) > ((k+1)-2)(\omega -1),$ we shall reach a contradiction by constructing a path $(v_1, v_2, \ldots , v_{k+1})$ induced in G. Technically, we define nested sets

$V(G) \supset V(G_1) \supset \cdots \supset V(G_i)$ and vertices $v_1 \in V(G_1), v_2 \in V(G_2), \ldots ,$$v_i \in V(G_i)$ for all i satisfying $1 \le i \le k-1$ with the following properties:

• (i) $G_i$ is a connected subgraph of G; 

• (ii) $\chi (G_i) > (k-1-i)(\omega -1);$

• (iii) if $1 \le j < i$ and $v \in V(G_i),$ then $v_jv$ is an edge of G if and only if $j = i-1$ and $v = v_i.$

For $i = 1$ we choose $G_1$ as a connected component of G with $\chi (G_1) > (k-1)(\omega -1)$ because $\chi (G) > (k-1)(\omega -1)$ was assumed. Let $v_1$ be any vertex of $G_1.$ Assume that $G_1, G_2, \ldots , G_i$ and $v_1, v_2, \ldots , v_i$ are already defined for some $i \le k-1;$ moreover, (i)–(iii) are satisfied. Define $G_{i+1}$ and $v_{i+1}$ as follows: Let A denote the set of neighbours of $v_i$ in $G_i.$ Let

$$\begin{aligned} B = V(G_i) \setminus (A \cup \{v_i\}). \end{aligned}$$

The graph $G_A$ induced by A in G satisfies $\omega (G_A) \le \omega -1$ because the presence of a $\omega$-clique in $G_A$ would give a $(\omega +1)$-clique in the subgraph induced by $A \cup \{v_i\},$ a contradiction. Furthermore, $G_A$ is $P_4$-free, since otherwise an induced $P_4$ in $G_A$ together with the vertex $v_i$ would induce a ${ gem}$, a contradiction. Hence $G_A$ is perfect and thus

$$\begin{aligned} \chi (G_A) = \omega (G_A) \le \omega (G)-1. \end{aligned}$$

Assume that $B \ne \emptyset .$ Now $\chi (G_i) \le \chi (G_A) + \chi (G_B),$ since a good colouring of $G_A$ with $\chi (G_A)$ colours, a good colouring of $G_B$ with $\chi (G_B)$ new colours and assignment of any colour used on $V(G_B)$ to $v_i$ define a good colouring of $G_i.$ Therefore

$$\begin{aligned} \chi (G_B)\ge & {} \chi (G_i) - \chi (G_A) > ((k+1)-1-i)(\omega -1) - (\omega - 1) \\= & {} ((k+1)-(i+1))(\omega - 1), \end{aligned}$$

which allows us to choose a connected component H of $G_B$ satisfying $\chi (H) > ((k+1)-(i+1))(\omega - 1).$ Since $G_i$ is connected by (i), there exists a vertex $v_{i+1} \in A$ such that $V(H) \cup \{v_{i+1}\}$ induces a connected subgraph which we choose as $G_{i+1}.$ Now it is easy to check that $G_1, G_2, \ldots , G_{i+1}$ and $v_1, v_2, \ldots , v_{i+1}$ satisfy the requirements (i)–(iii). Assume now that $B = \emptyset .$ Now $\chi (G_i) \le \omega -1,$ which implies $(k-i)(\omega -1) < \chi (G_i) \le (\omega -1).$

Consequently, $i = k.$ Since $A \ne \emptyset$ by properties (i) and (ii) of $G_i, v_{k+1}$ can be defined as any vertex of $A, G_{k+1} = v_{k+1},$ a contradiction. $\square$

Corollary 7

[18] Let G be a connected $(P_5, { gem})$-free graph of order n and clique number $\omega (G).$ Then $\chi (G) \le 6\omega (G).$

Corollary 8

[19] Let G be a connected $(P_6, { gem})$-free graph of order n and clique number $\omega (G).$ Then $\chi (G) \le 8\omega (G).$

Corollary 9

Let G be a connected $(P_k, R)$-free graph for some $k \ge 4$ with clique number $\omega (G),$ where $R \in \{{ paw}, { diamond}\}.$ Then $\chi (G) \le (k-2)(\omega (G)-1).$

For ${ triangle}$-free graphs both Theorem 33 and even Corollary 9 imply Corollary 1.

4.2 $\chi$-Polybound, $(2K_2, B)$-Free Graphs with Linear $\chi$-Binding Functions

Recall that there exists no linear $\chi$-binding function for the family of $2K_2$-free graphs and Wagon established a quadratic $\chi$-binding functions for this graph family. Now we summarize results mostly concerning $(2K_2, B)$-free graphs. Note that we already mentioned some graph families of this type in the previous sections attaining the Vizing bound. We start with a result of Fouquet, Giakoumakis, Maire and Thuillier. The ${ house}$ is the complement of the $P_5$ (see Fig. 1).

Theorem 34

[37] If G is a $(2K_2, { house})$-free graph, then $\chi (G) \le \frac{3}{2}\omega (G).$

We note that the graphs $K_s[C_5]$ sharpens the bound $\frac{3}{2}\omega$. Recently Karthick and Mishra [53] detected further linear $\chi$-bounded subfamilies of $2K_2$-free graphs.

Theorem 35

[53] Let G be a $2K_2$-free graph.

• If G is 4-wheel-free, then $\chi (G) \le \omega (G) + 5$

• If G is ${ HVN}$-free, then $\chi (G) \le \omega (G) + 3$

• If G is $K_5 - e$-free, then $\chi (G) \le \omega (G) + 4$

The special graphs ${ paw}$ and ${ HVN}$ can be generalized easily to a sequence of graphs $((K_1 \cup K_2)+K_p)$ for integers $p \ge 1,$ containing complete graphs minus two edges incident to the same vertex. The special graphs ${ diamond}$ ($K_4-e$) and $K_5-e$ can be generalized easily to a sequence of graphs $(2K_1+K_p)$ for integers $p \ge 1,$ containing complete graphs minus an edge. Brause et al. [13] recognised $(2K_2, 2K_1+K_p)$-free graphs containing larger cliques to be split graphs and $(2K_2, 2K_1+K_p)$-free graphs containing larger cliques to be multisplit graphs.

Theorem 36

[13] If G is a connected $(2K_2, 2K_1+K_p)$-free graph with $\omega (G) \ge 2p$ for some integer $p \ge 1,$ then G is a split graph.

The proof of Theorem 36 admits the following corollary.

Corollary 10

[13] For any integer $p \ge 0,$ the class of $(2K_2, 2K_1+K_p)$-free graphs has a linear $\chi$-binding function. In particular,

$$\begin{aligned} \chi (G) \le \omega (G) + (2p-1)(p-1). \end{aligned}$$

Theorem 37

[13] If G is a connected $(2K_2, (K_1 \cup K_2) +K_p)$-free graph with $\omega (G) \ge 2p$ for some integer $p \ge 2,$ then G is a multisplit graph.

The proof of Theorem 37 admits the following corollaries.

Corollary 11

[13] Let $p \ge 0$ be an integer and G be a $(2K_2, (K_1 \cup K_2) +K_p)$-free graph with $\omega (G) \ge 2p.$ If $p \ne 1$ or $\omega (G) \ne 2,$ then G is perfect.

Corollary 12

[13] For any integer $p \ge 0,$ the class of $(2K_2, 2K_1+K_p)$-free graphs has a linear $\chi$-binding function. In particular,

$$\begin{aligned} \chi (G) \le \omega (G) + (2p-1)(p-1). \end{aligned}$$

4.2.1 Non-existence of a Linear $\chi$-Binding Function for $(2K_2, 3K_1)$-Free Graphs

If G is a ${ claw}$-free graph with independence number $\alpha (G) = 2,$ then $\chi (G) \ge \frac{|V(G)|}{2}.$ But $\omega (G)$ may be of order $\sqrt{|V(G)| \cdot { log} |V(G)|}$ (cf. [58]). Now we turn to $(2K_2, { claw})$-free graphs with independence number $\alpha (G)=2.$ First of all, observe that this class can be equivalently defined as the class of $(2K_2, 3K_1)$-free graphs. Surprisingly, we can show that there is no linear $\chi$-binding function. For this purpose we consider the complement ${\overline{G}}$ of a graph G,  which is $K_3$-free and $C_4$-free. Hence $g({\overline{G}}) \ge 5.$ Now we apply the following result due to Bollobás. Here the maximum number of vertices of an independent set of a graph G is the independence number$\alpha (G)$ and $\frac{\alpha (G)}{|V(G)|}$ is the independence ratio of G. Let $i(\varDelta , g)$ be the infimum of the independence ratio of graphs with maximum degree $\varDelta$ and girth at least g.

Theorem 38

[8] If $\varDelta \ge 3$ and g are natural numbers, then $i(\varDelta , g) < 2({ log} \varDelta )/\varDelta$.

Hence, there exists a $(2K_2, 3K_1)$-free graph G with $\omega (G)/n(G) < 2({ log} \varDelta (G))/\varDelta (G).$ However, $\chi (G) \ge \frac{n(G)}{2}$ implying $\chi (G) > \frac{\varDelta }{4 log \varDelta } \cdot \omega (G).$ We immediately obtain the next result

Theorem 39

If G is a $(2K_2, 3K_1)$-free graph, then G has no linear $\chi$-binding function.

The proof given above admits an immediate generalization as follows.

Theorem 40

If R is a graph with independence number $\alpha (R) \ge 3,$ then there is no linear $\chi$-binding function for $\mathcal {G}(2K_2,R)$.

4.3 $\chi$-Polybound, (F, B)-Free Graphs with Linear $\chi$-Binding Functions and a Linear Forest F

Now we leave the trail of $2K_2$-free graphs and consider F-free graphs, where F is the linear forest $3K_1$ or $K_1 \cup P_4$ (also known as co-gem). We start with graphs having independence number $\alpha \le 2$. In terms of forbidden induced subgraphs these are $3K_1$-free graphs, sometimes called ${ triad}$-free graphs. This subfamily of ${ claw}$-free already turned out to be the intrinsic core of ${ claw}$-free graphs with respect to its chromatic properties and surely also doesn’t admit a linear $\chi$-bound. As shown by Chudnovsky and Seymour ${ claw}$-free graphs containing a ${ triad}$ satisfy the linear $\chi$-bound $2\omega$. In order to get a hereditary linear $\chi$-bounded subfamily of $3K_1$-free graphs, the linear forest $A=3K_1$ needs for instance the graph $B= K_1 \cup K_4$ as companion to be forbidden. Now we consider $(3K_1, K_1 \cup K_4)$-free graphs, which are also well known as complement of ${ triangle}$-free subcubic graphs. Choudum et al. [18] proved the following result.

Theorem 41

[18] If G is a connected $(3K_1, K_1 \cup K_4)$-free graph, then $\chi (G) \le 2\omega (G)$.

This has been improved by Henning, Löwenstein and Rautenbach to $\chi (G) \le \frac{3}{2}\omega (G)$ in [44], which is optimal. Again the graphs $K_s[C_5]$ sharpen the bound $\frac{3}{2}\omega$.

Theorem 42

[44] If G is a $(3K_1, K_1 \cup K_4)$-free graph, then $\chi (G) \le \frac{3}{2}\omega (G).$

4.3.1 $\chi$-Polybound, $(H, {\bar{H}} )$-Free Graphs with Polynomial $\chi$-Binding Functions and a Forest H (cf. [42])

The family of $(K_1 \cup P_4)$-free graphs has already been mentioned in Sect. 1.3.1. Karthick and Maffray were able to prove that (gem, co-gem)-free graphs are $\chi$-polybound. Moreover they detected the smallest $\chi$-binding function, since the sequence of lexicographic products $C_5[K_s]$ (of $C_5$ and $K_s$) of (gem, co-gem)-free graphs sharpen the bound $\frac{5}{4}\omega$.

Theorem 43

[52] Let $f^*$ denote the smallest $\chi$-binding function for the family of (gem, co-gem)-free graphs, then $f^*(\omega )=\frac{5}{4}\omega$

In [52] they posed the following open problem:

Problem 4

Determine the smallest $\chi$-binding function for the family of $(H, {\bar{H}} )$-free graphs, where H is a graph on at least five vertices different from the gem or co-gem.

Relaxing the optimality the problem is to find $\chi$-polybound families of graphs with forbidding a graph H and its complement ${\bar{H}}$. For graphs H with at most three vertices it is trivial. Let H be a graph having four vertices. Recall the necessary condition for the existence of a $\chi$-binding function that at least one forbidden graph, say H has to be acyclic. Let H be a graph having four vertices. All variations of $H \subset P_4$ lead to perfect graphs, especially for $H=P_4$ since $P_4$ is self-complementary $(P_4, \bar{P_4})$-free graphs are obviously $P_4$-free graphs with $f_{P_4}(\omega )=\omega$. In Theorem 25 we already considered the family of $(2K_2,C_4)$-free graphs. Blázsik et al. showed that these graphs attain the Vizing bound. The remaining cases with four vertices are $(K_4, 4K_1)$-free graphs settled by the Ramsey number R(4, 4), (co-diamond, diamond)-free graphs addressed in Theorem 31 in a slightly larger case, (co-paw, paw)-free graphs addressed in Corollary 2 in a slightly larger case, (claw, co-claw)-free graphs⁵ being $\chi$-polybound since ${ claw}$-free graphs have this property. Besides (co-gem, gem)-free graphs on five vertices cases the class of $(P_5, \bar{P_5})$-free graphs has been examined by Fouquet, Giakoumakis, Maire and Thuillier.

Theorem 44

[37] If G is a $(P_5, \bar{P_5})$-free graph, then $\chi (G) \le {\omega +1\atopwithdelims ()2}.$

Fouquet et al. detected based on a structural characterisation of $(P_5, \bar{P_5})$-free graphs⁶ a non-linear, quadratic $\chi$-binding function ${\omega +1\atopwithdelims ()2}$ and also obtained an $O(n^4)$-algorithm to determine a colouring using $O(\omega ^2)$ colours for a $(P_5, \bar{P_5})$-free graph with n vertices. Thus the family of $(P_5, \bar{P_5})$-free graphs is $\chi$-polybound and $\chi$-polydet. Whether the $\chi$-binding function ${\omega +1\atopwithdelims ()2}$ is best possible is an open question, but in [37] also an infinite sequence of $(P_5, \bar{P_5})$-free graphs G satisfying $\chi (G)\ge \omega (G)^c$ with $c=log_25-1$ were given.

4.4 Even-Hole-Free Graphs

Some further nice examples of graph families having a linear $\chi$-binding function can be found whilst examining even-${ hole}$-free graphs.

Odd-signable graphs have been introduced in [16]. We sign a graph by assigning 0, 1 weights to its edges. A graph is odd-signable if there exists a signing that makes the sum of the weights in every chordless cycle (including triangles) odd. To characterise odd-signable graphs in terms of excluded induced subgraphs, we now introduce two types of 3-path configurations (3 PC) and even ${ wheels}$. Let x and y be two distinct vertices of G. A 3PC(x, y) is a graph induced by three chordless xy-paths, such that any two of them induce a ${ hole}$. We say that a graph G contains a $3PC(\cdot ,\cdot )$ if it contains a 3PC(x, y) for some $x, y \in V(G)$. The $3PC(\cdot ,\cdot )$ are also known as ${ thetas}$. Let $x_1, x_2, x_3, y_1, y_2, y_3$ be six distinct vertices of G such that ${x_1, x_2, x_3}$ and ${y_1, y_2, y_3}$ induce ${ triangles}$. A $3PC(x_1x_2x_3, y_1y_2y_3)$ is a graph induced by three chordless paths $P_1=x_1, \ldots , y_1,P_2=x_2, \ldots , y_2$ and $P_3=x_3, \ldots , y_3,$ such that any two of them induce a ${ hole}$. We say that a graph G contains a $3PC(\triangle ,\triangle )$ if it contains a $3PC(x_1x_2x_3, y_1y_2y_3)$ for some $x_1, x_2, x_3, y_1, y_2, y_3 \in V(G)$. The $3PC(\triangle ,\triangle )$ are also known as prisms. A ${ wheel}$, denoted by (C, x),  is a graph induced by a ${ hole}$C and a vertex $x \notin V(C)$ having at least three neighbours in C,  say $x_1, \ldots , x_n$. A subpath of C connecting $x_i$ and $x_j$ is a sector if it contains no intermediate vertex $x_l, 1 \le l \le n$. A ${ wheel}$ (C, x) is even if it has an even number of sectors. It is easy to see that even ${ wheels}$, ${ thetas}$ and ${ prisms}$ cannot be contained in even-${ hole}$-free graphs. In fact they cannot be contained in odd-signable graphs. The following characterisation of odd-signable graphs states that the converse also holds, and it is an easy consequence of a theorem of Truemper [78].

Theorem 45

[32] A graph is odd-signable if and only if it does not contain an even ${ wheel}$, a ${ theta}$ or a ${ prism}$.

A bisimplicial vertex is a vertex whose set of neighbours induces a graph that is a union of two cliques. Addario-Berry et al. were able to prove the existence of a bisimplicial vertex in an even-${ hole}$-free graph. This property ensures easily the existence of a linear $\chi$-binding function for this graph family.

Theorem 46

[1] Every even-${ hole}$-free graph has a bisimplicial vertex.

Corollary 13

[1] If G is even-${ hole}$-free then $\chi (G) \le 2\omega (G)-1.$

The following result has been shown by Kloks et al. [59].

Theorem 47

[59] Let G be an $({ even}$-${ hole, diamond})$-free graph. Then G has a bisimplicial vertex and $\chi (G) \le \omega (G)+1.$

Fraser, Hamel and Hoàng recently generalized this result to the family of (even-hole, kite)-free graph. The ${ kite}$ is a supergraph of the ${ diamond}$ and is also known as co-chair (see Fig. 6). They characterised connected (even-hole, kite)-free graphs, i.e. an (even-hole, kite)-free graph is a ${ diamond}$-free graph, or is the join of a clique and a ${ diamond}$-free graph, or contains a clique cutset. Here a clique cutsetC of a graph G is a vertex subset of G inducing a clique and disconnecting G.

Theorem 48

[38] Let G be an (even-hole, kite)-free graph. Then $\chi (G) \le \omega (G)+1.$

A ${ pan}$ is a graph that consists of a ${ hole}$ and a single vertex with precisely one neighbour on the ${ hole}$. Cameron et al. showed that the family of (even-hole, pan)-free graphs is $\chi$-bounded.

Theorem 49

[14] An (even-hole, pan)-free graph satisfies $\chi (G) \le \frac{3}{2}\omega (G).$

A ${ cap}$ is a graph that consists of a ${ hole}$C and a vertex x that has exactly two neighbours in C, that are furthermore adjacent. Cameron et al. recently established also a $\frac{3}{2}\omega$ bound for $\chi (G)$ for (even-hole, cap)-free graphs and they expect an improvement towards $\frac{5}{4}\omega$.

Theorem 50

[16] An (even-hole, cap)-free graph satisfies $\chi (G) \le \frac{3}{2}\omega (G).$

Problem 5

[16] Is it true that $\chi (G) \le \lceil \frac{5}{4}\omega (G)\rceil$ for every (even-hole, cap)-free graph G?

5 $\chi$-Polybound Graphs with Non-linear $\chi$-Binding Functions

In previous sections we already mentioned a lot of examples of $\chi$-polybound graphs with non-linear $\chi$-binding functions. A ${ banner}$ is a graph that consists of a ${ hole}$C containing four vertices and a vertex x that has exactly one neighbour in C (see Fig. 6). Hoàng proved the following nice result.

Theorem 51

[45] If G is a (banner, odd-hole)-free graph, then $\chi (G) \le$${\omega (G)+1}\atopwithdelims (){2}$.

A subfamily of (banner, odd-hole)-free graphs is the class of $P_3\cup K_1$-free and $C_5$-free graphs, i.e. co-paw- and ${ 5-hole}$-free graphs. Hoàng and McDiarmid [46] were able to improve the exponent in the upper bound.

Theorem 52

[46] If G is $(P_3\cup K_1, C_5)$-free, then $\chi (G) \le \omega ^{\frac{3}{2}}(G)$

The proofs of the last results rely on an interesting concept called k-divisibilty introduced by Hoàng and McDiarmid [46]. A graph G is k-divisible if for each induced subgraph H of G with at least one edge, there is a partition of the vertex set of H into sets $V_1,\ldots ,V_k$ such that no $V_i$ contains a maximum clique of H. In [46] they proved that a ${ claw}$-free graph is 2-divisible if and only if it does not contain an odd ${ hole}$ and obtained Theorem 52.

Observation 5

[46] If every member G of a family ${{\mathcal {G}}}$ of graphs is k-divisible for a fixed k, then $\chi (G) \le k^{\omega (G)-1}$ and therefore ${{\mathcal {G}}}$ is $\chi$-bounded.

Therefore the following conjecture strengthens the Gyárfás–Sumner conjecture.

Conjecture 3

(Hoàng–McDiarmid conjecture [46]) Let F be any forest on k vertices. Then any graph G that does not contain F as induced subgraph is k-divisible.

In [45] Hoàng used a nice technique, a refinement of 2-divisibility, in order to prove Theorem 51. A graph is called perfectly divisible if every induced subgraph H of G contains a set X of vertices such that X meets all largest cliques of H, and X induces a perfect graph (cf. Observation 1). This matches perfectly to $\chi$-polybound families of graphs, i.e. let ${{\mathcal {G}}}$ be a family of graphs such that every member is perfectly divisible, then ${{\mathcal {G}}}$ is $\chi$-polybound.

Observation 6

[45] A perfectly divisible graph G satisfies $\chi (G) \le$${\omega (G)+1}\atopwithdelims (){2}$. If every member of ${{\mathcal {G}}}$ is perfectly divisible, then ${{\mathcal {G}}}$ is $\chi$-polybound,

[45] Hoàng proved Theorem 51 by showing that (banner, odd-hole)-free graphs are perfectly divisible. In [22] Chudnovsky and Sivaraman proved that $(P_5,C_5)$-free graphs are 2-divisible. Using Observation 5 yields the following result.

Theorem 53

[22] Every $(P_5,C_5)$-free graph satisfies $\chi (G) \le 2^{\omega (G)-1}$.

Two other subfamilies of $P_5$-free are also $\chi$-bounded, since they are perfectly divisible and by applying Observation 6. The ${ bull}$ is the unique (self complementary) graph on five vertices with degree sequence 33211.

Theorem 54

[22] Let G be a $P_5$-free graph. If G is ${ bull}$-free or odd ${ hole}$-free, then G satisfies $\chi (G) \le$${\omega (G)+1}\atopwithdelims (){2}$. Thus the corresponding graph families are $\chi$-polybound.

Another interesting approach towards $\chi$-binding functions has been achieved by Chudnovsky, Penev, Scott and Trotignon. In [25] they showed that if a graph family ${{\mathcal {G}}}$ is $\chi$-bounded, then likewise the closure of ${{\mathcal {G}}}$ under one of the three operations substitution, glueing along a clique or glueing along a bounded number of vertices is $\chi$-bounded. Moreover, if ${{\mathcal {G}}}$ is $\chi$-polybound, then the closure of ${{\mathcal {G}}}$ is likewise $\chi$-polybound. Analogously an exponential $\chi$-bound for a graph class ${{\mathcal {G}}}$, will likewise lead to an exponential $\chi$-bound for the closure of a graph class ${{\mathcal {G}}}$.

5.1 $\chi$-Polybound Subfamilies of $P_5$-Free Graphs with Non-linear $\chi$-Bound

Recall that so far only an exponential $\chi$-binding function is known for the class of $P_5$-free graphs. Previously we mentioned some subfamilies of $P_5$-free graphs having a linear $\chi$-binding function. In Theorem 54 we already mentioned two examples of subfamilies of $P_5$-free graphs having quadratic $\chi$-binding functions. Now we continue with further non-linear ones.

A structural characterisation of $2K_2$-free graphs has been shown recently by Dhanalakshmi et al. and lead to superclasses of $2K_2$-free graphs

Theorem 55

[33] Let G be a connected graph. Then G is $2K_2$-free if and only if G is $(P_5, { butterfly,hammer})$-free.

This characterisation evokes the two graph classes of $(P_5, { butterfly})$-free graphs and of $(P_5, { hammer})$-free graphs, which are both superclasses of $2K_2$-free graphs and subclasses of $P_5$-free graphs. $\chi$-binding functions for $(P_5, { butterfly})$-free graphs have been considered by Schiermeyer.

Theorem 56

[72] If G is a $(P_5, { butterfly})$-free graph, then $\chi (G) \le c \cdot \omega ^3(G)$ for some fixed constant c.

$\chi$-binding functions for the class of $(P_5, { hammer})$-free graphs have been considered by Brause et al.

Theorem 57

[13] If G is a $(P_5, { hammer})$-free graph, then $\chi (G) \le \omega ^2(G).$

Since the house is the complement of $P_5$ we restate here a result for a further subfamily of $P_5$-free graphs due to Fouquet et al. [37] mentioned in Theorem 44: IfGis a$(P_5,{ house})$-free graph, then$\chi (G) \le {\omega (G)+1\atopwithdelims ()2}.$

In Theorem 33 a linear bound for the class of $(P_k, { gem})$-free graphs was given. In case of $k=5$ the result says “IfGis a$(P_5, { gem})$-free graph, then$\chi (G) \le 3(\omega (G)-1)$”. In [71] the subgraph gem was replaced by the supergraph ${ gem}^+ = K_1 + (K_1 \cup P_4)$ also called ${ parachute}$ (see Figs. 1, 3).

Theorem 58

[71] If G is a $(P_5, { gem}^+)$-free graph, then $\chi (G) \le \omega ^2(G).$

Since ${ claw}$, ${ dart}$ and ${ cricket}$ (see Fig. 3) are induced subgraphs of the $gem^+$, we obtain the following corollary.

Corollary 14

[71] Let G be a $(P_5, H)$-free graph, where $H \in \{{ claw}, { dart},$${ cricket}\}.$ Then $\chi (G) \le \omega ^2(G).$

Brause et al. proved the following result for the family of $P_5$-free and $K_{2,t}$-free graph. Here $K_{2,t}$-free is a complete bipartite graph with partitions of size 2 and t.

Theorem 59

[11] Let G be a $(P_5, K_{2,t})$-free graph for some $t \ge 2.$ Then $\chi (G) \le c_t \cdot \omega ^t(G)$ for a constant $c_t.$

Sketch of proof

By the Strong Perfect Graph Theorem every non-perfect $(P_5, K_{2,t})$-free graph contains an induced $C_5$ or an induced ${\overline{C}}_{2p+1}$ for some $3 \le p \le \omega .$ We first consider the neighbourhood $N(C_5)$ of the $C_5,$ which can be partitioned into 21 distinct subsets depending on the neighbours on an induced $C_5.$ Using the Ramsey number $R(K_{\omega },K_t)$ we manage to find an induced $K_{2,t}$ or to show that $\chi (G) \le c(n_1) \cdot \omega ^t(G).$ Next we consider the neighbourhood of an induced ${\overline{C}}_{2p+1}$ and proceed in a similar way. $\square$

Next we make use of a structural result for connected $P_5$-free graphs from Bacsó and Tuza.

Theorem 60

[3] Every connected $P_5$-free graph contains a dominating clique or a dominating $P_3.$

This admits the following result for $P_5$-free graphs.

Theorem 61

[11] Let H be a graph such that ${{\mathcal {G}}}(H)$ has an $O(\omega ^s)$$\chi$-binding function for some $s \ge 1$, and let G be a connected $(P_5, K_1 + H)$-free graph. Then G has an $O(\omega ^{s+1})$$\chi$-binding function.

So we can apply Theorem 61 to obtain the following result for $(P_5, K_{2,t})$-free graphs.

Theorem 62

[11] Let G be a $(P_5, K_p + K_{2,t})$-free graph for some $p \ge 1, t \ge 2.$ Then $\chi (G) \le c(p,t) \cdot \omega ^{t+p}(G)$ for a constant c(p, t).

We continue with a generalization of Theorem 9 for $P_k$-free graphs.

Theorem 63

[72] Let G be a $(P_k, K_{n_1} \cup K_{n_2})$-free graph for some $n_1 \ge n_2 \ge 2.$ Then $\chi (G) \le c(n_1) \cdot \omega ^{n_1}(G)$ for a constant $c(n_1).$

Theorem 63 can be generalized to $(P_k, K_{n_1} \cup K_{n_2} \cup \cdots \cup K_{n_p})$-free graphs for $p \ge 3$ and $n_1 \ge n_2 \ge \cdots \ge n_p$ as follows. We use the proof above as an induction step with the following modification. For a subset $T \subset V(F)$ with $|T|=n_1$ the subgraph G[M(T)] is $(P_k, K_{n_2} \cup \cdots \cup K_{n_p})$-free. Hence $\chi (G[M(T)]) \le c(n_2, \ldots , n_p) \cdot \omega ^{\sum _{i=2}^{p-1}n_i},$ which leads to

$$\begin{aligned} \chi (G) \le \omega + \sum _{t=2}^{n_1-1}{\omega \atopwithdelims ()t}f_{P_k}(t) + {\omega \atopwithdelims ()n_1} \cdot c(n_2, \ldots , n_p) \cdot \omega ^{\sum _{i=2}^{p-1}n_i}, \end{aligned}$$

which is a polynomial of degree $\sum _{i=1}^{p-1}n_i$ in $\omega .$ So we obtain the following result.

Theorem 64

[72] Let G be a $(P_k, K_{n_1} \cup K_{n_2} \cup \cdots \cup K_{n_p})$-free graph for some $p \ge 2$ and $n_1 \ge n_2 \ge \cdots \ge n_p \ge 2.$ Then $\chi (G) \le c(n_1, \ldots , n_p) \cdot \omega ^{\sum _{i=1}^{p-1}n_i}$ for a constant $c(n_1, \ldots , n_p).$

Theorem 63 also leads to the following variation.

Theorem 65

[72] Let G be a $(P_k, K_{n_1} \cup P_4)$-free graph for some $n_1 \ge 2.$ Then $\chi (G) \le c(n_1) \cdot \omega ^{n_1+1}(G)$ for a constant $c(n_1).$

The counterpart of Theorem 10 for $P_k$-free graphs is the following.

Theorem 66

[72] Let H be a graph such that ${{\mathcal {G}}}(H)$ has an $O(\omega ^t)$$\chi$-binding function for some $t \ge 1$, and let G be a $(P_k, K_{n_1} \cup H)$-free graph for some $n_1 \ge 2.$ Then $\chi (G) \le c(n_1,H) \cdot \omega ^{n_1+t}(G)$ for a constant $c(n_1,H).$

Now we consider $(P_5, { windmill})$-free graphs. For integers $r, p \ge 2$ the ${ windmill}$$W_{r+1}^p = K_1 + pK_r$ is the graph obtained by joining a single vertex (the center) to the vertices of p disjoint copies of a complete graph $K_r$ (the windmill$W_3^2$ is shown in Fig. 2). For integers $n_1 \ge n_2 \ge \cdots \ge n_p \ge 2,$ the ${ generalized}$${ windmill}$$W(n_1, n_2, \ldots , n_p) = K_1 + (K_{n_1}\cup K_{n_2}\cup \cdots \cup K_{n_p})$ is the graph obtained by joining a single vertex (the center) to the vertices of p disjoint complete graphs $K_{n_1}, \ldots , K_{n_p}$ (see Fig. 2).

Based on Theorem 60 the following result for $P_5$-free graphs has been achieved.

Theorem 67

[72] Let H be a graph such that ${{\mathcal {G}}}(H)$ has an $O(\omega ^t)$$\chi$-binding function for some $t \ge 1$, and let G be a connected $(P_5, K_1 + H)$-free graph. Then G has an $O(\omega ^{t+1})$$\chi$-binding function.

So we can apply Theorem 67 to obtain the following results for $(P_5, { windmill})$-free graphs.

Theorem 68

[72] Let G be a $(P_5, W(n_1, n_2))$-free graph for some $n_1 \ge n_2 \ge 2.$ Then $\chi (G) \le c(n_1) \cdot \omega ^{n_1+1}$ for a constant $c(n_1).$

Theorem 69

[72] Let G be a $(P_5, W(n_1, n_2, \ldots , n_p))$-free graph for some $p \ge 2$ and $n_1 \ge n_2 \ge \ldots \ge n_p \ge 2.$ Then $\chi (G) \le c(n_1, \ldots , n_p) \cdot \omega ^{1+\sum _{i=1}^{p-1}n_i}(G)$ for a constant $c(n_1, \ldots , n_p).$

6 Miscellaneous

In 1985, Gyárfás [42] made three beautiful and well-known conjectures. They all have been proved now by Chudnovsky, Scott, Seymour, and Spirkl and thus became theorems.

Theorem 70

[74] For every integer $k > 0$ there exists n(k) such that every graph G with no clique of cardinality more than k and no odd hole has chromatic number at most n(k).

Theorem 71

[27] For all integers $k,l > 0$ there exists n(k, l) such that every graph G with no clique of cardinality more than k and no hole of length more than l has chromatic number at most n(k, l).

Theorem 72

[29] For all integers $k,l > 0$ there exists n(k, l) such that every graph G with no clique of cardinality more than k and no odd hole of length more than l has chromatic number at most n(k, l).

The third result evidently contains the other two results.

7 Concluding Remarks

This survey continues in a certain sense our previous survey on vertex colouring and forbidden subgraphs [69] with a stronger emphasis on polynomial $\chi$-binding functions. There are overlaps of polynomial$\chi$-binding functions and forbidden induced subgraphs and other topics of graph theory, which could not be addressed here in more details. We refer the interested reader to graph colorings with local constraints—a survey by Tuza [79], graphs on surfaces by Mohar and Thomassen [61], perfect graphs by Ramirez-Alfonsin and Reed [65], graph colourings and the probabilistic method by Molloy and Reed [62], Some problems on induced subgraphs by Sivaraman, even-hole free graphs: a survey by Vušković [80], graph colouring problems by Jensen and Toft [49], a survey on the computational complexity of coloring graphs with forbidden subgraphs by Golovach, Johnson, Paulusma and Song [40] and graph classes: a survey by Brandstädt, Le and Spinrad [9] . We close this survey hoping that many researchers will continue/follow the trail of finding polynomial $\chi$-binding functions $f(\omega )$ for graph families accompanied by the problem of determining a colouring requiring at most $f(\omega )$ colours, i.e. the study of $\chi$-polybound and $\chi$-polydet graph families.