Open Problems on Graph Coloring for Special Graph Classes

Abstract

For a given graph G and integer k, the Coloring problem is that of testing whether G has a k-coloring, that is, whether there exists a vertex mapping $c: V\rightarrow \{1,2,\ldots \}$ such that $c(u)\ne c(v)$ for every edge $uv\in E$. We survey known results on the computational complexity of Coloring for graph classes that are hereditary or for which some graph parameter is bounded. We also consider coloring variants, such as precoloring extensions and list colorings and give some open problems in the area of on-line coloring.

The author was supported by EPSRC (EP/K025090/1).

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Graph coloring is a central topic in Computer Science due to a high number of theoretical and practical applications. Within both structural and algorithmic graph theory, many graph coloring variants and generalizations have been studied. Besides the well-known text-book of Toft and Jensen [65], several survey papers appeared over the years. For instance, the survey of Tuza [70] considered the graph coloring problem and variants of it, in which local restrictions are imposed on the coloring (e.g. precoloring extensions and list colorings) whereas the survey of Randerath and Schiermeyer [61] considered structural and complexity aspects of graph colorings for hereditary graph classes.

As graph coloring and many of its variants are computationally hard on general graphs, it is natural to restrict the input graph to some special graph class. This topic has been extensively studied in the literature. A recent survey of Golovach et al. [27] updated several parts of the two aforementioned survey papers [61, 70] and the survey of Chudnovsky [13] by primarily focussing on computational complexity aspects of graph coloring for graph classes characterized by one or two forbidden induced subgraphs. As noted by Golovach et al. [27], the task to collect complexity results for graph coloring restricted to other graph classes might be beyond the scope of a single paper. Our aim is therefore to discuss a number of such results and open problems not mentioned in [27]. In particular we will identify a number of gaps in existing complexity results.

The survey is organized as follows. In Sect. 2 we state some terminology. Then, in Sect. 3, we consider the (classical) complexity of graph coloring, precoloring extension and list colorings for a number of graph classes characterized by more than two forbidden induced subgraphs and also for some graph classes for which some graph parameter is bounded. We discuss parameterized coloring problems in Sect. 4 and on-line coloring problems in Sect. 5. We briefly consider graph homomorphisms in Sect. 6.

Fig. 1.

Relationships between Coloring and its variants as shown in [27]. An arrow from one problem to another indicates that the latter is a special case of the former; k and $\ell$ are any two integers for which $\ell \ge k$.

2 Preliminaries

A coloring of a graph $G=(V,E)$ is a vertex mapping $c: V\rightarrow \{1,2,\ldots \}$ with the additional condition that $c(u)\ne c(v)$ whenever $uv\in E$. We call c(u) the color of u. If $1\le c(u)\le k$ for all $u\in V$ then c is also called a k-coloring of G. We say that G is k-colorable if a k-coloring of G exists. The chromatic number $\chi (G)$ of G is the smallest integer k for which G is k-colorable. The Coloring problem is that of deciding whether a graph G is k-colorable for some given integer k. If k is fixed (that is, not part of the input) we obtain the k-Coloring problem.

A k-precoloring of a graph $G=(V,E)$ is a mapping $c_W: W\rightarrow \{1,2,\ldots k\}$ for some subset $W\subseteq V$. We say that a k-coloring c of G is an extension of a k-precoloring $c_W$ of G if $c(v)=c_W(v)$ for each $v \in W$. For a given graph G, a positive integer k and a k-precoloring $c_W$ of G, the Precoloring Extension problem asks whether $c_W$ can be extended to a k-coloring of G. If k is fixed we denote this problem as the k -Precoloring Extension problem.

A list assignment of a graph $G=(V,E)$ is a function L with domain V such that for each vertex $u\in V$, L(u) is a subset of $\{1, 2, \dots \}$. This set is called the list of admissible colors for u. If $L(u)\subseteq \{1,\ldots ,k\}$ for each $u\in V$ then L is also called a k-list assignment. The size of a list assignment L is the maximum list size |L(u)| over all vertices $u\in V$. A coloring c respects L if $c(u)\in L(u)$ for all $u\in V$. This leads to the following three problems. Given a graph G with a list assignment L, the List Coloring problem is that of testing whether G has a coloring that respects L. If inputs are restricted to pairs (G, L) where L has size at most $\ell$ then we obtain the $\ell$-List Coloring problem, and if each L is a k-list assignment, we obtain the List k -Coloring problem. See Fig. 1 for a display of the relationships between the seven problems defined above.

Let G be a graph and $\{H_1,\ldots ,H_p\}$ be a set of graphs. Then G is said to be $(H_1,\ldots ,H_p)$-free if G has no induced subgraph isomorphic to a graph in $\{H_1,\ldots ,H_p\}$. If $p=1$, we may write that G is $H_1$-free. The disjoint union $(V(G)\cup V(H), E(G)\cup E(H))$ of two vertex-disjoint graphs G and H is denoted by $G+H$ and the disjoint union of r copies of a graph G is denoted by rG. The complement $\overline{G}$ of a graph G has vertex set $V(\overline{G})=V(G)$ and an edge between two distinct vertices u and v if and only if u and v are not adjacent in G. We denote the path and cycle on n vertices by $P_n$ and $C_n$, respectively.

Let G be a connected graph. The distance d(u, v) between two vertices u and v in G is the number of edges in a shortest path from u to v in G. The diameter of G is the maximum of $\max _{v}d(u,v)$ over all vertices u in G. The radius of G is the minimum of $\max _{v}d(u,v)$ over all vertices u in G.

Let p be a graph parameter and let $\mathcal{G}$ be a graph class. We say that $\mathcal{G}$ has bounded p if there exists a constant c such that $p(G) \le c$ for all $G\in \mathcal{G}$.

3 Classical Complexity

The problems k-Coloring, k-Precoloring Extension, List k -Coloring and k-List Coloring are polynomial-time solvable for general graphs if $k\le 2$ and NP-complete if $k\ge 3$ [52, 67]. As mentioned, we refer to the recent survey [27] for an overview of known results for these problems when restricted to H-free graphs and $(H_1,H_2)$-free graphs. In this section we consider a number of other graph classes.

Cycle-free Graphs. A hole is a cycle of on at least four vertices. An antihole is the complement of a hole. A cycle, hole or antihole is even if it contains an even number of vertices; otherwise it is odd. An (anti)hole is long if it has at least five vertices. A graph is odd-hole-free or odd-antihole-free if it contains no induced odd holes or no induced odd antiholes, respectively. In a similar way we define (even-)hole-free, (even-)antihole-free, long-hole-free, long-antihole-free, odd-cycle-free and (odd-)anticycle-free graphs.

Grötschel et al. [30] proved that Coloring is polynomial-time solvable for perfect graphs, or equivalently (due to the Strong Perfect Graph Theorem [14]) for graphs that are odd-hole-free and odd-antihole-free. Note that hole-free graphs and antihole-free graphs are perfect. Hence Coloring is also polynomial-time solvable for hole-free graphs and antihole-free graphs, and thus for cycle-free graphs (forests) and anticycle-free graphs (coforests).

Král’ et al. [49] proved that Coloring is NP-complete for $(2P_2,C_5)$-free graphs and also for $(C_3,C_4,C_5)$-free graphs. Consequently, Coloring is NP-complete for long-hole-free graphs and long-antihole-free graphs, and thus for odd-hole-free graphs and odd-antihole free graphs. In contrast, Coloring is polynomial-time solvable for odd-cycle-free graphs (bipartite graphs) and odd-anticycle-free graphs (cobipartite graphs). If we change the parity of the forbidden cycles from odd to even, then we obtain two long-standing open problems; we refer to the survey of Vušković [68] for more on even-cycle-free graphs (even-hole-free graphs).

Open Problem 1

Determine the complexity of Coloring for even-cycle-free graphs and even-anticycle-free graphs.

Table 1. The complexity of k-Precoloring Extension and List k -Coloring on $P_t$-free bipartite graphs for fixed k and t.

Bipartite and Chordal Bipartite Graphs. A graph is chordal bipartite if it is bipartite and every induced cycle has exactly four vertices. Hujter and Tuza [41] proved that Precoloring Extension is linear-time solvable on $P_5$-free bipartite graphs (which are chordal bipartite) and NP-complete for $P_{6}$-free chordal bipartite graphs. Kratochvíl [50] answered two of their open problems [40] by proving that 3-Precoloring Extension is NP-complete for planar bipartite graphs and that 5-Precoloring Extension is NP-complete for $P_{14}$-free bipartite graphs. The latter result was strengthened by Huang et al. [39], who proved that, for all $k\ge 4$, k-Precoloring Extension is NP-complete for $P_{10}$-free chordal bipartite graphs. The same authors [39] also proved that List 4-Coloring is NP-complete for $P_8$-free chordal bipartite graphs.

Brandstädt et al. [5] proved that the class of $(C_3,P_6)$-free graphs has bounded clique-width. By combining their result with results of Kobler and Rotics [48] and Oum and Seymour [62] we find that, for all $k\ge 1$, List k -Coloring is polynomial-time solvable on $(C_3,P_6)$-free graphs (see also e.g. [39]). Table 1 summarizes the above results for $P_t$-free bipartite graphs.

Open Problem 2

Determine the complexity of the problems k-Precoloring Extension and List k -Coloring for the missing cases in Table 1.

Huang et al. [39] posed the following two open problems.

Open Problem 3

Determine the complexity of the problems List 3-Coloring and 3-Precoloring Extension for the class of chordal bipartite graphs.

Planar Graphs and Graphs of Bounded Vertex Degree. To recall two classic results, Garey et al. [26] proved that 3-Coloring is NP-complete even for planar graphs of maximum degree 4, whereas every planar graph is 4-colorable by the Four Color Theorem [2]. Chlebík and Chlebíková [12] strengthened the aforementioned result of Kratochvíl [50] for planar bipartite graphs by proving that 3-Precoloring Extension is NP-complete even for planar bipartite graphs of maximum degree 4. The same authors [12] also showed that List 3-Coloring is NP-complete for 3-regular planar bipartite graphs but that Precoloring Extension is polynomial-time solvable for arbitrary graphs of maximum degree at most 3.

Demange and de Werra [17] proved that 3-Precoloring Extension is NP-complete for subgrids (which are induced subgraphs of grids and hence have maximum degree at most 4) and that List 3-Coloring is NP-complete even for subgrids of maximum degree at most 3, whereas Kratochvíl and Tuza [51] showed that List Coloring is polynomial-time solvable for graphs of maximum degree 2. Demange and de Werra [17] also proved that List 4-Coloring is NP-complete for grids, and they posed the following open problem.

Open Problem 4

Determine the complexity of Precoloring Extension for grids.

When consider graphs of bounded degree that are not necessarily planar a full complexity classification is known (see [16]) for Coloring, List Coloring and Precoloring Extension and also for k-List Coloring, List k -Coloring and k -Precoloring Extension. However, no dichotomy is known for k-Coloring restricted to graphs of maximum degree at most d, but some partial results have been obtained. Molloy and Reed [60] classified the complexity for all pairs (k, d) for sufficiently large d, whereas Emden-Weinert et al. [19] showed that k -Coloring is NP-complete for graphs of maximum degree at most $k+\lceil \sqrt{k}\rceil -1$. By combining the latter result with Brooks’ Theorem [8], we find that the smallest open case is the following problem.

Open Problem 5

Determine the complexity of 5-Coloring for graphs of maximum degree 6.

Graphs of Bounded Diameter. By using a reduction from 3-Coloring via adding dominating vertices one can easily show that k-Coloring is NP-complete for graphs of diameter d for all pairs (k, d) with $k\ge 3$ and $d\ge 2$ except for two notorious cases, namely $(k,d)\in \{(3,2),(3,3)\}$. Mertzios and Spirakis [57] settled the case $(k,d)=(3,3)$. They proved that, for every $0\le \epsilon <1$, 3-Coloring is NP-complete even for classes of triangle-free graphs $G=(V,E)$ of diameter 3, radius 2 and minimum degree $\delta =\varTheta (|V|^\epsilon )$.

We note that, for every $k\ge 1$ and $p\ge 1$, the problems k -Coloring and k -Precoloring Extension are polynomially equivalent on the class of graphs of diameter at most p. This can be seen as follows. Firstly, k-Coloring is a special case of k -Precoloring Extension. Secondly, if we are given a graph G of diameter at most p with a k-precoloring $c_W$ for some $W\subseteq V(G)$, then we identify any two vertices of W that are colored alike. Afterwards all precolored vertices have a distinct color and we add an edge between any two of them that are not adjacent already. This results in a graph $G'$ of diameter p and a k-precoloring $c'_{W'}$ defined on some subset $W'\subseteq V(G')$, such that $c'_{W'}$ can be extended to a k-coloring of $G'$ if and only if $c_W$ can be extended to a k-precoloring of G. Moreover, the set $W'$ forms a clique of size at most k in $G'$ meaning that we may just as well uncolor these vertices, that is, $c'_{W'}$ can be extended to a k-coloring of $G'$ if and only if $G'$ is k-colorable. Hence we only need to consider:

Open Problem 6

Determine the complexity of the problems 3-Coloring and List 3-Coloring for graphs of diameter 2.

Graphs of Bounded Asteroidal Number. An asteroidal triple in a graph is a set of three mutually non-adjacent vertices such that each two of them are joined by a path that avoids the neighborhood of the third. An asteroidal set in a graph G is an independent set $S\subseteq V(G)$, such that every set of three vertices of S forms an asteroidal triple. The asteroidal number is the size of a largest asteroidal set in G. Note that graphs with asteroidal number at most 2 have no asteroidal triple. These graphs are also known as AT-free graphs. Stacho [63] proved that 3-Coloring is polynomial-time solvable on AT-free graphs. Later, Kratsch and Müller [53] extended this result by showing that even List k -Coloring is polynomial-time solvable on these graphs for every fixed integer $k\ge 1$. Marx [56] proved that Precoloring Extension is NP-complete for proper interval graphs, which form a subclass of AT-free graphs. It follows from a result of Jansen [42] (see [28]) that $\ell$-List Coloring ($\ell \ge 3$) is NP-complete for $3P_1$-free graphs, and thus for AT-free graphs. However, the following problem, posed by Broersma et al. [7] in 1999, is still open.

Open Problem 7

Determine the complexity of Coloring for AT-free graphs.

Král’ et al. [49] proved that Coloring is NP-complete for $4P_1$-free graphs and thus for graphs with asteroidal number at most 3.

Open Problem 8

Determine, for every $k\ge 3$ and $p\ge 3$, the complexity of k-Coloring, k-Precoloring Extension and List k -Coloring on graphs with asteroidal number at most p.

4 Parameterized Coloring Problems

A problem is called fixed-parameter tractable (FPT) if every instance (I, p) of it can be solved in time $f(p)|I|^{O(1)}$ where f is a computable function that only depends on p. If k -Coloring is polynomial-time solvable for some graph class $\mathcal{G}$ for every integer k (and Coloring is not known to be polynomial-time solvable for $\mathcal{G}$) then k is a natural parameter to consider. We refer to [27] for a survey on parameterized complexity results (and open problems) with this parameter for classes of graphs characterized by one or two forbidden induced subgraphs. Here, we only mention the following open problem of Kratsch and Müller [53].

Open Problem 9

Is Coloring fixed-parameter tractable for AT-free graphs when parameterized by k?

Because 3-Coloring is NP-complete in general, other parameters have been considered. For instance, Marx [55] proved that PreColoring Extension parameterized by the number of precolored vertices is W[1]-hard for interval graphs. We survey a number of other results below (see also Table 2).

Arnborg and Proskurowski [3] proved that Coloring is FPT when parameterized by the treewidth of the input graph. Fellows et al. [21] showed that Precoloring Extension and List Coloring are W[1]-hard with this parameter. On the positive side, List Coloring is polynomial-time solvable for any graph class of bounded treewidth, as shown by Jansen and Scheffler [44].

It is known [15] that the clique-width of a graph G is at most $2^{{{\mathrm{tw}}}(G)-1}$, where ${{\mathrm{tw}}}(G)$ denotes the treewidth of G. Moreover, by combining results of Kobler and Rotics [48] and Oum and Seymour [62], one finds that Coloring is polynomial-time solvable for any graph class of bounded clique-width. Hence, it is natural to research whether one can improve the FPT result for Coloring from treewidth to clique-width. However, Fomin et al. [24] showed that Coloring is W[1]-hard when parameterized by the clique-width of the input graph. We also note that Precoloring Extension is NP-complete for distance-hereditary graphs [4], which have clique-width at most 3 [29].

The vertex cover number of a graph G is the size of a smallest subset $U\subseteq V(G)$, such that $G-U$ is edgeless. Fiala et al. [23] proved that, with this parameter, Precoloring Extension is FPT and List Coloring is W[1]-hard even for split graphs. It can be observed [23] that the treewidth of a graph is at most its vertex cover number. Hence, the aforementioned result of Jansen and Scheffler [44] implies that List Coloring is polynomial-time solvable for any graph class of bounded vertex cover number.

The twin cover number of a graph G is the size of a smallest subset $U\subseteq V(G)$, such that every two adjacent vertices in $G-U$ have the same closed neighborhood in G; note that $G-U$ is a disjoint union of cliques. Ganian [25] proved that Precoloring Extension is FPT when parameterized by the twin cover number of the input graph. As the twin cover number of a graph is at most its vertex cover number (by definition), this result strengthens the aforementioned result of Fiala, Golovach and Kratochvíl [23]. For the same reason, List Coloring is W[1]-hard when parameterized by the twin cover number.

The cluster vertex deletion number of a graph G is the size of a smallest subset $U\subseteq V(G)$, such that $G-U$ is a disjoint union of cliques. Note that the cluster vertex deletion number of a graph G is at most its twin cover number. However, in contrast to the aforementioned FPT result of Ganian [25], Doucha and Kratochvíl [18] proved that Precoloring Extension is W[1]-hard when parameterized by the cluster vertex deletion number of the input graph. The same authors [18] also showed that Coloring is FPT with this parameter. It is easily seen that List Coloring is polynomial-time solvable for any graph class $\mathcal{G}$ of bounded cluster vertex deletion number. We guess a coloring of the set U of a graph $G\in \mathcal{G}$ that respects the given list of each vertex of U. We then remove all vertices of U from G after adjusting the lists of the vertices in $G-U$ accordingly. As $G-U$ is a disjoint union of cliques we can solve List Coloring in polynomial time (see e.g. [9]). Since |U| is bounded, the maximum number of colorings of U that we need to guess is polynomial. Hence, the result follows.

For an integer $c\ge 1$, the c-bounded cluster vertex deletion number of a graph G is the size of a smallest subset $U\subseteq V(G)$, such that $G-U$ is a disjoint union of cliques of size at most c. Doucha and Kratochvíl [18] proved that, for every fixed integer $c\ge 1$, Precoloring Extension is FPT when parameterized by the c-bounded cluster vertex deletion number of the input graph.

Table 2. The complexity of Coloring, Precoloring Extension and List Coloring for various graph parameters. All problems are in XP for each parameter except when para-NP-complete. The relationships, as given in [18], between rows 1–6 are: $1 \le 2 \le 4\le 6$ and $1\le 3\le 5\le 6$ and $3\le 4$, where $x\le y$ means that parameter x is bounded by (some function of) parameter y. Hence, membership in FPT or XP for a problem with parameter x carries over to y, and W[1]-hardness for y carries over to x.

Recently, Aboulker et al. [1] considered the number $p_k$ of vertices of degree at least $k+1$ of the graph G in an instance (G, k) of Coloring. This parameter is motivated by Brooks’ theorem [8]: if $p_k(G)=0$ then G is k-colorable unless G is a complete graph or an odd cycle. They showed that Coloring is FPT when parameterized by $p_k$.

We now discuss some graph classes that fall under the “distance from triviality” framework, introduced by Guo et al. [31]. For a graph class $\mathcal{F}$ and an integer p we define four classes of “almost $\mathcal{F}$” graphs, i.e. graphs that are, in some sense, “distance” p apart from $\mathcal{F}$, namely the classes $\mathcal{F}+pe$, $\mathcal{F}-pe$, $\mathcal{F}+pv$ and $\mathcal{F}-pv$, which consist of all graphs that can be modified into a graph of $\mathcal{F}$ by deleting at most p edges, adding at most p edges, deleting at most p vertices and adding at most p vertices, respectively. As Grötschel et al. [30] proved that Coloring is polynomial-time solvable on perfect graphs, Coloring was studied from a parameterized point of view for various subclasses $\mathcal{F}$ of perfect graphs. We survey a number of these results below. For every result mentioned, p is the chosen parameter (see also Table 3 for an overview). In this context a modulator of a graph is a set of at most p edges or vertices whose removal or addition makes the graph a member of $\mathcal{F}$.

Table 3. The complexity of Coloring, when parameterized by p, for classes close to some subclass $\mathcal{F}$ of perfect graphs. The polynomial and FPT cases hold even if a modulator is not part of the input.

Cai [9] proved that Coloring is FPT on split$+pe$ graphs and W[1]-hard for split$+pv$ graphs. The same author [9] also proved that whenever Coloring is polynomial-time solvable on a graph class $\mathcal{F}$ that is closed under edge contraction and a modulator is given, then Coloring is FPT on $\mathcal{F}-pe$. As a result, Coloring is FPT for split$-pe$ graphs, and also for interval$-pe$ graphs¹ and chordal$-pe$ graphs. Note that we obtain polynomial-time solvability for $\mathcal{F}-pv$ whenever $\mathcal{F}$ is a class of perfect graphs closed under vertex deletion(as in that case it holds that $\mathcal{F}-pv=\mathcal{F}$). Cai [9] also proved that Coloring is NP-complete for bipartite$+2v$ graphs and for bipartite$+3e$ graphs but linear-time solvable onbipartite$+1v$ and bipartite$+2e$ graphs. Marx [55] showed that Coloring is FPT ² on interval$+pe$ graphs and also on chordal$+pe$ graphs but W[1]-hard for interval$+pv$ graphs and for chordal$+pv$ graphs.

An (undirected) graph is a comparability graph if there exists an assignment of exactly one direction to each of its edges such that (u, w) is a directed edge whenever (u, v) and (v, w) are directed edges. Takenaga and Higashide [64] proved that Coloring, restricted to comparability$+pe$ graphs, is polynomial-time solvable for $p=1$ and NP-complete for $p\ge 2$. They also proved that Coloring is polynomial-time solvable on comparability$-1e$ graphs.

Open Problem 10

Determine the complexity of Coloring for the classes of comparability$-pe$ graphs and comparability$+pv$ graphs when parameterized by p.

We now consider the class of complete graphs. It is known that List Coloring is FPT for complete$-pe$ graphs [28]. We observe that List Coloring is polynomial-time solvable on complete$+pe$ graphs and complete$-pv$ graphs (because such graphs are complete and List Coloring is polynomial-time solvable even on block graphs [4]). In contrast to the aforementioned W[1]-hardness results of Coloring for split$+pv$, interval$+pv$ and chordal$+pv$ graphs, it holds that Coloring is FPT for complete$+pv$ graphs, as shown by Cai [9]. Golovach et al. [28] posed the following open problem.

Open Problem 11

Determine the complexity of List Coloring and Precoloring Extension for complete$+pv$ graphs when parameterized by p.

Jansen and Kratsch [43] and de Weijer [69] considered the k-Coloring problem for various graph classes $\mathcal{F}+pv$ in order to obtain polynomial kernels (also some negative results are shown, for instance, 3-Coloring on path$+pv$ has no polynomial kernel unless NP $\subseteq$ coNP/poly [43]).

5 On-Line Coloring

In this section we focus on the on-line setting of graph coloring. On-line coloring algorithms were introduced by Gyárfás and Lehel [35] to model a rectangle packing problem related to dynamical storage allocation. In this setting the graph is presented vertex by vertex according to some externally determined ordering. An on-line coloring algorithm irrevocably colors the vertices when they come in by using a strategy that depends only on the subgraph induced by the revealed vertices and their colors. A well-known example of an on-line coloring algorithm is First-Fit which assigns, starting from the empty graph, each new vertex the least color from $\{1,2, \ldots \}$ that does not appear in its neighborhood. We refer to the survey of Kierstead [45] for more details.

Non-surprisingly, the number of colors used by an on-line coloring algorithm for an arbitrary graph G can be much larger than the chromatic number of G. Below we define three measures for the performance of an on-line algorithm on graphs of some specified class $\mathcal{G}$after first giving some additional terminology.

Let AOL(G) be the (finite) set of all on-line coloring algorithms for a graph G. Let $\varPi (G)$ be the set of all permutations of the vertices of G. For $A \in AOL(G)$ and $\pi \in \varPi (G)$, let $\chi _A(G,\pi )$ denote the number of colors used by A when the vertices of G are presented to A according to $\pi$. The A-chromatic number $\chi _A(G)$ of G is the largest number of colors used by A to color G, that is,

$$\chi _A(G) = \max _{\pi \in \varPi (G)} \chi _A(G,\pi ).$$

An algorithm A is an on-line coloring algorithm for some graph class $\mathcal {G}$ if $A \in AOL(G)$ for every $G \in \mathcal {G}$. We let $AOL(\mathcal {G})$ be the set of on-line coloring algorithms for $\mathcal{G}$.

A natural performance measure for an on-line coloring algorithm, introduced by Gyárfás and Lehel [35], is to determine whether the number of colors it uses on any graph $G\in \mathcal{G}$ is bounded from above by a function that only depends on the chromatic number of G. Formally, for a graph class $\mathcal{G}$, we say that an algorithm $A \in AOL(\mathcal {G})$ is competitive if there exists a $\chi$-bounding function f, that is, a function f such that

$$\chi _A(G) \le f(\chi (G))\; \text{ for } \text{ every } G \in \mathcal {G}.$$

In that case $\mathcal{G}$ is said to be on-line $\chi$- bounded. For example, the class of $P_4$-free graphs is on-line $\chi$-bounded, because First-Fit colors every $P_4$-free graph G with $\chi (G)$ colors [35]. It is also known that First-Fit is competitive for interval graphs with a linear $\chi$-bounding function [46]. Consequently, the class of interval graphs is on-line $\chi$-bounded as well. Every class of graphs with bounded independence number [11] is also on-line $\chi$-bounded, just as the class of $P_5$-free graphs [33]. In fact, Gyárfás and Lehel [33] proved a stronger statement, namely that the class of $P_5$-free graphs is on-line $\omega$-bounded, that is, there exists an on-line coloring algorithm A and a function g, called an $\omega$-bounding function, such that $\chi _A(G) \le g(\omega (G))$ for every $P_5$-free graph G. This result has been extended by Kierstead et al. [47] who proved that, for every tree T of radius at most 2, the class of T-free graphs is on-line $\omega$-bounded (with a superexponential $\omega$-bounding function). As a special case of their result we find that the class of cocomparability graphs is on-line $\omega$-bounded. More recently, Felsner et al. [22] gave a cubic $\omega$-bounding function for a subclass of cocomparability graphs, namely for the class of intersection graphs of convex sets spanned between two lines (their algorithm uses the intersection representation as input).

Despite all the above results there exist many graph classes, such as the class of trees [35], for which no competitive on-line coloring algorithm exists. These negative results lead to a natural definition of a weaker form of competitiveness, namely on-line competitiveness, which is defined as follows. The on-line chromatic number $\chi _{OL}(G)$ of G is the smallest number of colors used by any on-line coloring algorithm for G, that is,

$$\chi _{OL}(G) = \min _{A \in AOL(G)} \chi _A(G).$$

Then, for a graph class ${\mathcal G}$, an algorithm $A \in AOL(\mathcal {G})$ is said to be on-line competitive if there exists a function h such that

$$\chi _A(G) \le h(\chi _{OL}(G))\; \text{ for } \text{ every } G \in \mathcal {G}.$$

In that case $\mathcal{G}$ is said to be on-line $\chi _{OL}$-bounded. This performance measure was coined by Gyárfás et al. [32], who proved that the class of graphs with girth at least 5 is on-line $\chi _{OL}$-bounded, but results of this type have been obtained before the term was formally introduced. For instance, Gyárfás and Lehel [34] proved that, for any tree T, First-Fit uses $\chi _{OL}(T)$ colors.

By combining known and new results, Broersma et al. [6] proved that, for all bipartite graphs H on at most five vertices, the class of H-free bipartite graphs is on-line $\chi _{OL}$-bounded. If H has six or more vertices the situation is not clear. For instance it is not known whether the class of $C_6$-free bipartite graphs is on-line $\chi _{OL}$-bounded. In fact this is not even known for its subclass of chordal bipartite graphs.

Open Problem 12

Is the class of chordal bipartite graphs on-line $\chi _{OL}$-bounded?

Now consider $P_t$-free bipartite graphs. Broersma et al. [6] proved that the class of $P_7$-free bipartite graphs is on-line $\chi _{OL}$-bounded. The algorithm behind their result is based on a certain way of coloring the vertices of a complete bipartite graph with classes $\{u_1,\ldots ,u_m\}$ and $\{v_1,\ldots ,v_m\}$ minus a perfect matching $\{u_1v_1, u_2v_2 \ldots , u_mv_m\}$. If the ordering is $u_1,v_1,u_2,v_2,\ldots ,u_m,v_m,$ then First-Fit assigns colors $1,1,2,2,\ldots ,m,m$, so m colors in total. However, assigning colors 1, 1, 2, 3 to the first four vertices $u_1,v_1,u_2,v_2$ in this ordering requires only three colors in total. The algorithm for $P_7$-free bipartite graphs expands on this approach and uses two disjoint lists of colors for the bipartition classes of each connected component in the subgraph revealed so far. Then, whenever two connected components are glued together by an incoming vertex, it tries to prevent the “mixing” of these color lists as much as possible. Recently, Micek and Wiechert refined and extended this approach. In this way they could prove that the classes of $P_8$-free bipartite graphs [58] and even $P_9$-free bipartite graphs [59] are on-line $\chi _{OL}$-bounded. This leads to the following open problem.

Open Problem 13

Is the class of $P_k$-free bipartite graphs on-line $\chi _{OL}$-bounded for every $k\ge 1$?

As $P_5$-free graphs and $P_6$-free bipartite graphs are on-line $\omega$-bounded and on-line $\chi _{OL}$-bounded, respectively, the following problem from [6] is of interest as well.

Open Problem 14

Is the class of $(C_3,P_6)$-free graphs on-line $\chi _{OL}$-bounded?

Solving Open Problems 12–14 may lead to new on-line $\chi _{OL}$-bounded classes of graphs. Unlike the competitive variant, no negative results are known.

Open Problem 15

Is the class of all graphs on-line $\chi _{OL}$-bounded?

6 Conclusions

We surveyed a number of results and open problems for Coloring for restricted graph classes. We did so both in an off-line and on-line setting and also considered the more general variants Precoloring Extension and List Coloring. Another way of generalizing the concept of graph coloring is to consider graph homomorphisms. A graph homomorphism from a graph G to a graph H is a mapping $f: V(G)\rightarrow V(H)$ such that $f(u)f(v)\in E_H$ whenever $uv\in E_G$. For a fixed graph H, the problem H -Homomorphism tests whether a given graph G allows a homomorphism to H. If we choose H to be the complete graph on k vertices, then this problem is equivalent to k -Coloring. We refer to the survey of Hell and Nešetřil [37] for more on graph homomorphisms.

The classical result in the area of graph homomorphisms is the Hell-Nešetřil dichotomy theorem [38] which states that H-Homomorphism is solvable in polynomial time if H is bipartite, and NP-complete otherwise. It is a natural question whether tractability results can be obtained for non-bipartite graphs H when the input is restricted to some graph class. Not so many results are known in this direction for hereditary graph classes, but to give an example, Enright et al. [20] proved that, for every fixed graph H, the list version of H-Homomorphism is polynomial-time solvable for a superclass of graphs that contains the classes of permutation graphs and interval graphs.