The Robust Chromatic Number of Graphs

We consider finite simple graphs \(G=(V,E)\), without loops and multiple edges. Sometimes the notation V(G) and E(G) will also be used. For a graph G its chromatic number \(\chi (G)\) is the minimum number k such that there exists a coloring \(c:V(G)\rightarrow \{1,2,\dots ,k\}\) with \(c(u)\ne c(v)\) whenever \((uv)\in E(G)\), its clique number \(\omega (G)\) is the largest number of vertices that form a complete subgraph (clique) of G, its independence number \(\alpha (G)\) is the largest number of vertices that induce an empty subgraph (independent set, stable set) of G, and its clique covering number \(\theta (G)\) is the smallest number of complete subgraphs whose union contains all vertices of G.

Definition 1

1. (i)

   A 1-selection in a graph \(G=(V(G),E(G))\) is a mapping \(f:V(G)\rightarrow E(G) \cup \{\varnothing \}\) such that \(v\in f(v)\) holds for all \(v\in V(G)\) with \(f(v)\ne \varnothing \). The graph \(G_f\) with vertex set \(V(G_f)=V(G)\) and edge set

   $$\begin{aligned} E(G_f):= E(G) {\setminus } f(V(G)) \end{aligned}$$

   is termed a 1-removed subgraph of G.

2. (ii)

   A graph is unicyclic if it contains at most one cycle. We call a graph quasi-unicyclic if each of its components is a tree or a unicyclic graph.

A transparent representation of a 1-selection f can be given by a directed graph D(G, f) whose vertex set is V(G), and for each \(v\in V(G)\) with a non-empty image the selection \(f(v)=vw\) is represented as the arc (v, w), which is oriented from v to w. Hence directed cycles of length 2 may also occur. According to the definitions, all vertices have out-degree at most 1 in D(G, f). For this reason the underlying undirected graphs of D(G, f) for 1-selections f are quasi-unicyclic.

We introduce the following graph invariants concerning 1-removed subgraphs.

Definition 2

For a graph G,

• the 1-robust chromatic number of G is \( \chi _1(G):= \min _f \chi (G_f), \)

• the 1-robust clique number of G is \( \omega _1(G):= \min _f \omega (G_f), \)

• the 1-robust independence number of G is \( \alpha _1(G):= \max _f \alpha (G_f), \)

• the 1-robust clique covering number of G is \( \theta _1(G):= \max _f \theta (G_f), \)

• the 1-robust chromatic index of G is \( \chi _1'(G):= \min _f \chi '(G_f), \)

where \(\min \) and \(\max \) are taken over all 1-selections f on G.

The following proposition collects some basic properties of the 1-robust chromatic number. The proofs are immediate from the definitions.

Proposition 1

1. (i)

   The value \(\chi _1(G)\) of a graph \(G=(V,E)\) is equal to the minimum number k of vertex classes in a partition \(V=V_1\cup \cdots \cup V_k\) such that each \(V_i\) induces a quasi-unicyclic subgraph in G.

2. (ii)

   A graph G satisfies \(\chi _1(G)=1\) if and only if it is quasi-unicyclic. In particular, every tree has \(\chi _1=1\).

3. (iii)

   If \(G=(V,E)\) does not have any tree components, then in computing \(\chi _1(G)\) one may restrict attention to 1-selections f that are injective, i.e. \(f(v)\ne f(v')\) for any two distinct \(v,v'\in V\), without loss of generality.

Due to (i), \(\chi _1\) corresponds to a weakening of the condition that defines “vertex arboricity”, as in the latter only a subfamily of 1-selections is allowed; cf. Sect. 1.2 and later Proposition 6.

In fact, the above notions can be put in a more general setting.

Definition 3

For a non-negative integer s, an s-selection on a graph \(G=(V, E)\) is defined as a function \(f: V \rightarrow 2^E\) such that \(f(v)\subseteq E(v)\) and \(|f(v)|\le s\) where E(v) refers to the set of edges incident with vertex v. Using this definition, one can introduce various graph parameters like \(\chi _s(G)\), \(\omega _s(G)\), \(\alpha _s(G)\), etc. as defined in Definition 2 by taking the minimum or maximum value over all s-selections.

With this formalism the chromatic number, the clique number, the independence number, and the clique covering number of G may be viewed as \(\chi (G)=\chi _0(G)\), \(\omega (G)=\omega _0(G)\), \(\alpha (G)=\alpha _0(G)\), and \(\theta (G)=\theta _0(G)\), respectively. Then standard inequalities generalize as follows.

Proposition 2

For every graph G and every integer \(s\ge 0\) we have

moreover

Simplified terminology. In the sequel we concentrate on the case of \(s=1\), leaving the larger values of s for later research. For this reason, we will just write “robust” instead of “1-robust” for each of the parameters \(\chi _1\), \(\omega _1\), \(\alpha _1\), \(\theta _1\), \(\chi _1'\).

Example 1

If G is the complete graph \(K_n\), which has \(\chi (G) = \omega (G) = n\), then \(\chi _1(G)=\omega _1(G)=\lceil n/3 \rceil \). The lower bound \(\omega _1(G)\ge \lceil n/3 \rceil \) is a direct consequence of Turán’s theorem, as at most n edges are removed using a 1-selection. The upper bound \(\chi _1(G)\le \lceil n/3 \rceil \) is easily seen by splitting the vertex set into \(\lceil n/3 \rceil \) disjoint sets \(V_1,\dots ,V_{\lceil n/3 \rceil }\) of sizes at most 3, and removing all edges inside each \(V_i\).

Example 2

Let \(t>k\ge 2\) be any integers. If G is the complete k-partite graph \(K_{t,\dots ,t}\), then of course \(\chi (G) = \omega (G) = k\). But we also have \(\chi _1(G)=\omega _1(G)=k\). Indeed, G contains \(t^k\) copies of \(K_k\), and each edge is contained in exactly \(t^{k-2}\) copies of \(K_k\). The number of vertices is kt, hence by removing that many edges, no more than \(kt \cdot t^{k-2}=kt^{k-1}\) copies of \(K_k\) can be destroyed and the clique number remains k.

Below we shall see that the conclusion \(\chi _1(G)=\omega _1(G)=k\) is valid also for \(t=k\) if \(k\ge 3\). (This is not the case if \(k=2\) because \(\chi _1(K_{2,2}) = \chi _1(C_4) = 1\).)

1.1 Motivation and Earlier Results

The robust chromatic number \(\chi _1\) was introduced in [12] as a useful tool to derive estimates on a Turán-type extremal problem on graphs where edges are assigned with sets of integer vectors. As it might help in other extremal graph theoretic problems, we think it is worth investigating this graph parameter and its analogues in more details. Our definitions always ask how much we can alter the original chromatic / independence / etc. numbers by deleting a 1-selection; we are interested in the largest possible change achievable for a given graph. Similar alterations of graph parameters have already been studied. The ones that are closest to the 1-robust chromatic number are the vertex arboricity (introduced in [2]) and linear arboricity (introduced in [6]) of a graph. There, color classes may induce forests or linear forests, while for the 1-robust chromatic, as Proposition 1 states, color classes may induce graphs with all components being unicyclic. A different, but also related, track of research asks for the “most vital” elements of a graph (without putting local restrictions on them), whose removal causes the greatest change in a specified parameter; see, e.g., [1] and the references therein.

The paper [12] established the following results on \(\chi _1\) for complete multipartite graphs and random multipartite graphs.

Theorem 1

1. (i)

   [12, Proposition 2.6.] The complete tripartite graph \(K_{r,s,t}\) with \(1 \le r \le s \le t\) and \(t\ge 2\) satisfies \(\chi _1(K_{r,s,t}) = 2\) if and only if \(r \le 2\); otherwise \(\chi _1(K_{r,s,t}) = \chi (K_{r,s,t}) = 3\). (If \(t=1\), for \(K_{1,1,1}\) we have \(\chi _1(K_{1,1,1}) = \chi _1(C_3) = 1\).)

2. (ii)

   [12, Theorem 1.10.] Let K(m, r, p) denote the probability space of all labeled r-partite graphs with each partite set having size m, where any two vertices in different parts are joined with probability p, independently of any other pairs. If \(p = \omega (m^{-1/\left( {\begin{array}{c}r\\ 2\end{array}}\right) })\), then \(\chi _1(K(m, r, p)) = r = \chi (K(m, r, p))\) with probability tending to 1 as m tends to infinity.

3. (iii)

   [12] A bipartite graph F has \(\chi _1(F)=2\) (i.e., \(\chi _1(F)=\chi (F)\)) if and only if it contains a component with more edges than vertices.

1.2 Standard Definitions and Notation

Beside \(\alpha ,\omega ,\chi ,\theta ,\chi '\) which already occurred above, we use the standard notation \(\delta (G)\) for minimum vertex degree and \(\Delta (G)\) for maximum vertex degree. Also, for two graphs G and H we write \(G \oplus H\) to denote their complete join if G and H are vertex-disjoint; and \(G\cup H\) will denote the graph with vertex set \(V(G)\cup V(H)\) and edge set \(E(G)\cup E(H)\), where \(V(G)\cap V(H)=\varnothing \) may or may not hold. The lexicographic product of G and H, denoted by \(G\circ H\), has vertex set \(V(G\circ H) = V(G) \times V(H)\); two vertices \((g',h'), (g'',h'') \in V(G\circ H)\) are adjacent if either \(g'g''\in E(G)\) or \(g'=g''\) and \(h'h''\in E(H)\).

Two less commonly known, yet still significant graph parameters, are defined as follows:

• a(G) represents the vertex arboricity of a graph G, which is defined as the minimum number a of vertex classes in a partition \((V_1,\dots ,V_a)\) of V(G) such that each \(V_i\) induces a forest in G.

• d(G) denotes the degeneracy of a graph G. It is the smallest non-negative integer d such that every induced subgraph \(G'\) of G satisfies \(\delta (G')\le d\).

1.3 Our Results

In Sect. 2, we study how basic graph operations—edge or vertex deletion, union and vertex-disjoint union, lexicographic product, or taking the line graph—act on the robust chromatic number.

Then in Sect. 3, we compare \(\chi _1(G)\) to some of the most commonly considered graph parameters. We summarize our findings in the theorem below.

Theorem 2

1. 1.

   For every graph G we have

   $$\begin{aligned}\Big \lceil \frac{\chi (G)}{3} \Big \rceil \le \chi _1(G) \le \chi (G)\end{aligned}$$

   and

   $$\begin{aligned}\Big \lceil \frac{\omega (G)}{3} \Big \rceil \le \omega _1(G) \le \omega (G).\end{aligned}$$

   All these bounds are tight, for all possible values of \(\chi \) and \(\omega \).

2. 2.

   For every graph G without isolated vertices,

   $$\begin{aligned}\theta (G)\le \theta _1(G)\le 3\theta (G)\end{aligned}$$

   and the upper bound is tight.

3. 3.

   For every graph G the bounds

   $$\begin{aligned}a(G)/2 \le \chi _1(G) \le a(G)\end{aligned}$$

   are valid and tight.

4. 4.

   Let k be any positive integer. If \(\Delta (G) < 3k\), then

   $$\begin{aligned}\chi _1(G)\le k,\end{aligned}$$

   that is,

   $$\begin{aligned}\chi _1(G) \le \Big \lceil \frac{\Delta (G)+1}{3} \Big \rceil .\end{aligned}$$

   Moreover, the bounds are tight for both \(\Delta \) and \(\chi _1\) as there exist graphs \(G_k\) with \(\Delta (G_k)=3k\) and \(\chi _1(G_k)=k+1\).

5. 5.

   Every d-degenerate graph G has

   $$\begin{aligned}\chi _1(G) \le d/2 + 1.\end{aligned}$$

   Moreover, this upper bound is tight as for every \(k\ge 1\) there exists a graph \(H_k\) such that \(H_k\) is 2k-degenerate and \(\chi _1(H_k)=k+1\).

6. 6.

   If \(\Delta (G)>1\), then

   $$\begin{aligned}\chi _1'(G)\le \chi '(G)-2.\end{aligned}$$

   Moreover,

   $$\begin{aligned}\delta (G) - 2 \le \chi _1'(G) \le \Delta (G) - 1.\end{aligned}$$

   All these bounds are tight.

Separate points of Theorem 2 will be proved in different subsections of Sect. 3.

One can observe that almost all inequalities in Theorem 2 are tight, except possibly the lower bound \(\theta _1\ge \theta \). Certainly, if G has no edges, then both \(\theta \) and \(\theta _1\) are equal to the order of G. We conjecture that \(\theta _1(G)=\theta (G)\) is characterized by these trivial examples.

Conjecture 1

The strict inequality \(\theta _1(G) > \theta (G)\) is valid, except for the trivial case where G is an edgeless (empty) graph.

In the present context it is also natural to introduce the following two algorithmic problems:

Robust k-colorability

Input: Graph \(G=(V,E)\), natural number k.

Question: Is \(\chi _1(G) \le k\) ?

Robust coloring

Input: Graph \(G=(V,E)\).

Solution: The value of \(\chi _1(G)\).

Due to the next result, which we prove in Sect. 4, it would be of great interest to identify graph classes in which \(\chi _1\) can be determined efficiently.

Theorem 3

For every natural number \(k\ge 3\), the Robust k-colorability problem is NP-complete. Moreover, Robust coloring is not approximable within \(O(|V|^{1/2-\varepsilon })\) for any real \(\varepsilon > 0\), unless P \(=\) NP.

On the positive side, we prove that \(\alpha _1,\omega _1,\chi _1,\theta _1\) are computable on graphs of bounded treewidth in linear time. Let us remark that according to Courcelle’s theorem [3] if a computational problem on graphs is expressible in monadic second-order logic, then on any class of graphs with bounded treewidth it is solvable in linear time. Several robust parameters can be described with a monadic second-order logic statement; but on the other hand, we think that explicit algorithms are more transparent than those derived from the framework of logic.

Many further questions are raised in the concluding section.

Vertex partition vs. edge decomposition.

We close the introduction with observations comparing the quasi-unicyclic partitions of vertex sets and edge sets. The parameter \(\chi _1\) asks about the minimum number of classes in a vertex partition of a graph into sets that induce quasi-unicyclic subgraphs. It turns out that edge decompositions into subgraphs of this kind have a completely different nature and can be handled in a more efficient way.

Theorem 4

1. 1.

   For any graph \(G=(V,E)\) the minimum number of quasi-unicyclic subgraphs \(H_1,\dots ,H_k\) with \(E(H_1)\cup \cdots \cup E(H_k) = E\) is equal to

   $$\begin{aligned} \max _{U\subseteq V} \Bigg \lceil \frac{e(G[U])}{|U|} \Bigg \rceil , \end{aligned}$$

   where e(G[U]) denotes the number of edges induced by U in G. Moreover, the minimum k and a corresponding edge decomposition can be determined in polynomial time.

2. 2.

   More generally, for every positive integer s the minimum number of s-selections decomposing the edge set of G is equal to

   $$\begin{aligned} \max _{U\subseteq V} \Bigg \lceil \frac{1}{s} \Bigg \lceil \frac{e(G[U])}{|U|} \Bigg \rceil \Bigg \rceil . \end{aligned}$$

Proof

It follows from a result of Hakimi [5, Theorem 4] that if \(G=(V,E)\) is an undirected graph and t is a positive integer such that each \(Y\subseteq V\) induces at most \(t\cdot |Y|\) edges in G, then G admits an orientation with maximum out-degree at most t. For later history, references and short proofs of the general form of Hakimi’s theorem we refer to Section 2.2 of [14]. Once an orientation of this kind with \(t=\max _{U\subseteq V} \Big \lceil \frac{e(G[U])}{|U|} \Big \rceil \) is at hand for G, we can partition the edge set into t classes so that the out-going edges at each vertex belong to mutually distinct classes. Then each class forms a graph with all vertices having out-degree 0 or 1, thus each edge class is a quasi-unicyclic graph. In the general case, \(\lceil \frac{t}{s}\rceil \) classes are enough (and also needed) as one class may contain s outgoing edges from each vertex.

Concerning the cited known results it is also known that an orientation minimizing the maximum out-degree can be obtained by using maximum matching algorithms in bipartite graphs. This yields a solution in polynomial time. \(\square \)

The following result collects the effect of some frequently studied operations on graphs.

Theorem 5

(i):

[Edge deletion, vertex deletion.] The invariants \(\alpha _1, \omega _1, \chi _1, \theta _1\) are monotone with respect to graph inclusion, in the following way.

If G is any graph and H is a spanning subgraph of G, then

$$\begin{aligned} \alpha _1(G) \le \alpha _1(H),\qquad \theta _1(G) \le \theta _1(H), \end{aligned}$$

and if H is any subgraph of G, then

$$\begin{aligned} \omega _1(G) \ge \omega _1(H),\qquad \chi _1(G) \ge \chi _1(H). \end{aligned}$$

(ii):

[Vertex-disjoint union]

If G is disconnected and \(G_1, \dots , G_k\) are its connected components, then

$$\begin{aligned} \chi _1(G)= & {} \max _{1\le i\le k} \chi _1(G_i),\qquad \omega _1(G) = \max _{1\le i\le k} \omega _1(G_i), \\ \alpha _1(G)= & {} \sum _{i=1}^k \alpha _1(G_i),\qquad \theta _1(G) = \sum _{i=1}^k \theta _1(G_i). \end{aligned}$$

(iii):

[Union of two graphs] If \(V(G_1)=V(G_2)\), then

$$\begin{aligned} \chi _1(G_1\cup G_2) \le \min \left\{ \chi (G_1) \chi _1(G_2), \, \chi _1(G_1) \chi (G_2) \right\} , \end{aligned}$$

and the bound is tight.

(iv):

[General graph union]

If \(G_1, \dots , G_k\) are graphs on the same vertex set, then

$$\begin{aligned} \chi _1(G_1\cup \cdots \cup G_k) \le (2k+1) \prod _{i=1}^{k} \chi _1(G_i). \end{aligned}$$

Moreover, there exist graphs \(G_1, \dots , G_k\) such that

$$\begin{aligned} \chi _1(G_1\cup \cdots \cup G_k) \ge \frac{2k+1}{3} \prod _{i=1}^{k} \chi _1(G_i). \end{aligned}$$

(v):

[Lexicographic product] For any two graphs G and H we have \(\chi _1(G\circ H) \le \chi (G) \cdot \chi _1(H)\).

(vi):

[Line graph]

Contrary to the notion of proper coloring, the unary operation \(G\mapsto L(G)\) does not admit a direct correspondence between robust edge colorings of G and robust vertex colorings of L(G); in particular, \(\chi _1'(G)=\chi _1(L(G))\) does not hold in general.

Proof

1. (i)

   It suffices to note that the inequalities \(\alpha (G) \le \alpha (G-e)\), \(\chi (G) \ge \chi (G-e)\), \(\omega (G) \ge \omega (G-e)\), \(\theta (G) \le \theta (G-e)\) hold for every graph \(G=(V,E)\) and every edge \(e\in E\).

2. (ii)

   The equalities follow by choosing an optimal 1-selection in each component of G.

3. (iii)

   It suffices to take a 1-selection in one of the two graphs, and apply the fact that \(\chi \) is a submultiplicative function. Tightness is shown by the following example. For \(p,q\ge 3\) with \(3p\ge q\), we partition \(G=K_{3pq}\) into the complete q-partite graph \(G_1=K_{3p,3p,\dots ,3p}\) and the disjoint union of q cliques, \(G_2=qK_{3p}\). Then \(\chi _1(G)=pq\), \(\chi (G_1)=\chi _1(G_1)=q\), \(3\chi _1(G_2)=\chi (G_2)=3p\), and so \(pq=\min \{\chi (G_1)\chi _1(G_2),\chi _1(G_1)\chi (G_2)\}=\min \{qp,q\cdot 3p\}\).

4. (iv)

   For \(i=1,\dots ,k\) let \(F_i\) be the edge set in an optimal 1-selection \(f_i\) on \(G_i\) (optimal in the sense that \(\chi (G_i-F_i)=\chi _1(G_i)\)). Then any subset X of the vertex set induces at most |X| edges of \(F_i\), hence the average degree in every induced subgraph of

   $$\begin{aligned} F:= F_1\cup \cdots \cup F_k \end{aligned}$$

   is at most 2k. As a consequence, \(\chi (F) \le 2k+1\). Thus, writing the union in the form

   $$\begin{aligned} G_1\cup \cdots \cup G_k = F \cup (G_1-F_1) \cup \cdots \cup (G_k-F_k) \end{aligned}$$

   and applying the multiplicative property of \(\chi \), the upper bound follows. A simple example showing the claimed lower bound is obtained from a Hamiltonian decomposition of the complete graph \(K_{2k+1}\). This yields k Hamiltonian cycles, which we can take as \(G_1,\dots , G_k\). Then of course \(\chi _1(G_i)=1\) holds for every i, while, as Example 1 shows, we have \(\chi _1(K_{2k+1})=\lceil \frac{2k+1}{3}\rceil \).

5. (v)

   For every \(g\in V(G)\) the vertex subset \(V_g:= \{ (g,h) \mid h\in V(H) \}\) induces a subgraph isomorphic to H in \(G\circ H\). Choose an optimal 1-selection \(f:V(H)\rightarrow E(H)\) of H, and copy it into each \(V_g\), hence creating a 1-selection \(f_{G\circ H}\). Removing the edge set \(f_{G\circ H} V(G\circ H)\) from \(G\circ H\), each \(V_g\) admits a partition into independent sets \(V_{g,i}\) for \(i=1,\dots ,\chi _1(H)\). Hence we can consider a proper vertex coloring \(\varphi :V(G)\rightarrow \{1,\dots ,\chi (G)\}\) of G with the minimum number of colors, and decompose \(V(G\circ H)\) into the sets \(\bigcup _{g\in S} V_{g,i}\) where S runs over the color classes of \(\varphi \). Clearly, each of those \(\chi (G) \cdot \chi _1(H)\) sets is independent in \((G\circ H) - f_{G\circ H} V(G\circ H)\), verifying the validity of the assertion.

6. (vi)

   As a small example, \(L(K_4)=K_6-3K_2\), hence \(\chi _1(L(K_4))=2\), while removing the 1-selection \(C_4\subset K_4\) we obtain \(2K_2\), therefore \(\chi _1'(K_4)=1\). As an infinite class, the stars \(K_{1,m}\) have \(\chi _1'(K_{1,m})=1\) and \(\chi _1(L(K_{1,m}))=\chi _1(K_m)=\lceil m/3 \rceil \). \(\square \)

It should be noted that the two invariants in (v) are not interchangeable; that is, \(\chi _1(G) \cdot \chi (H)\) is not an upper bound on \(\chi _1(G\circ H)\). Simple counterexamples are obtained by taking sufficiently large edgeless graphs for H.

In this section, we compare the robust parameters \(\omega _1\), \(\theta _1\), and \(\chi _1\) with several important graph invariants.

3.1 Clique Number

Proposition 3

For every graph G we have

and

All these bounds are tight, for all possible values of \(\chi \) and \(\omega \).

Proof

The upper bounds follow directly from the definitions. Also the lower bound in (2) is implied by the property of complete graphs shown in Example 1. For the lower bound in (1), let \(k=\chi _1(G)\) and consider the color classes \(V_1,\dots ,V_k\) of a subgraph \(G_f\) of G, where \(k=\chi (G_f)=\chi _1(G)\). By Proposition 1(i), the induced subgraph \(G[V_i]\) is unicyclic and therefore 3-colorable for all \(i \in [k]\). Thus, each \(V_i\) can be partitioned into at most three sets that are independent in G, and this way we obtain a color partition of G with at most \(3k=3\chi _1(G)\) color classes. This shows \(\chi (G)\le 3\chi _1(G)\) and the lower bound follows.

Tightness is shown for any value of \(\chi \) by Examples 1 and 2. \(\square \)

In fact, there are much wider classes of graphs establishing equality in either side of (1), as it will be proved in the sequel.

3.2 Clique Covering Number

Here we deal with the robustness parameter \(\theta _1(G)\) corresponding to \(\theta (G)\).

Proposition 4

For every isolate-free graph G,

and the upper bound is tight.

Proof

It is evident to note that for every graph G, the inequality \(\theta _1(G)\ge \theta (G)\) holds. For the proof of the upper bound \(3\theta (G)\) let us take a minimum cover (co-coloring) of G and let Q be an arbitrary class in it. Consider any 1-selection S of G as a graph. It is more convenient to work with the complement of the graph. The subgraph of S induced by Q has chromatic number at most 3 as all the cycles and forests are 3-colorable. Thus, if we return to G and we delete S from Q, the subgraph obtained has co-chromatic number at most 3. Applying this for any class, we obtain the claimed bound.

Tightness is shown by the vertex-disjoint union of any cliques of sizes at least 3. Indeed, a triangle can be removed from each of those cliques. Then every original clique will need at least three cliques in a clique cover after the removal of a suitable 1-selection. \(\square \)

In the next part of the paper we study the tightness of the lower bound.

3.2.1 “Exact Graphs”: On the Equation \(\theta _1=\theta \)

The goal of this sub-subsection is to provide partial results towards Conjecture 1. Let us introduce the following term.

Definition 4

We call a graph G exact if \(\theta _1(G) = \theta (G)\).

As noted earlier, edgeless graphs are exact; and the conjecture states that no other graphs are. We are going to analyze the properties of a hypothetic counterexample.

Before formulating the results, let us give some (mostly standard) definitions, which will be used in the sequel.

Definition 5

Let \(G=(V,E)\) be any graph. Then

• G is critically k-co-chromatic if \(\theta (G)=k\) but \(\theta (G-x)=k-1\) holds for every \(x\in V\). Further, G is critical if it is critically k-co-chromatic for some k.

• G is imperfect if it contains an induced subgraph \(G'\) such that \(\chi (G')>\omega (G')\). Otherwise, G is a perfect graph.

• G is partitionable if, for every vertex a, the graph \(G-a\) can be represented as a rectangle where the rows are stable sets and the columns are cliques.

• G is uniquely co-colorable if every minimum co-coloring yields the same partition of V.

• A set \(W\subseteq V\) is an inducing set if it induces a quasi-unicyclic subgraph in G. We denote

  $$\begin{aligned}\iota (G):= \max \{|W|: W \ \text {is an inducing set in} \ G\}.\end{aligned}$$

• A set \(D\subseteq V\) is dominating in G if, for every \(x\in V-D\), x has at least one neighbor in D.

Let us note here that partitionable graphs played an important role in the theory of perfect graphs. They also yield good examples of critical graphs that are imperfect. However, we shall see that partitionable graphs are not exact and, on the other hand, nontrivial exact graphs—if there exist any—are not perfect. (Simple non-exact examples are chordless cycles and their complements: for even orders they are perfect, for odd orders they are partitionable.)

The following observation shows that it suffices to restrict the study of exact graphs to connected ones.

Proposition 5

A graph is exact if and only if all of its connected components are exact.

Proof

We recall from Theorem 5 (ii) that \(\theta _1\) is additive with respect to vertex-disjoint union, in the same way as the clique covering number \(\theta \) is additive. Hence, if \(\theta _1(G')=\theta (G')\) holds for each component \(G'\) of G, then also \(\theta _1(G)=\theta (G)\) is valid. On the other hand, if \(\theta _1(G')>\theta (G')\) in a component \(G'\), then additivity implies strict inequality in G, as well. \(\square \)

Based on this proposition, Conjecture 1 can be re-stated in the following simple form.

Conjecture 1\({\mathbf {'}}\) If G is a connected graph with more than one vertex, then G is not exact; i.e., the null-graph \(G=(\emptyset ,\emptyset )\) and the singleton \(K_1\) are the only exact graphs that are connected.

Some properties of nontrivial, connected, exact graphs are collected in the next result.

Theorem 6

Let \(G=(V, E)\) be a connected exact graph with at least two vertices. Then

(i):

G is critical;

(ii):

\(\theta (G) > \alpha (G)\);

(iii):

G is imperfect;

(iv):

for every vertex triple a, b, c of G, not all minimum co-colorings \(\varphi \) of \(G-a\) assign \(\varphi (b)=\varphi (c)\);

(v):

\(G-a\) is not uniquely co-colorable for any vertex \(a\in V\);

(vi):

G is not partitionable;

(vii):

\(\omega (G) \ge 3\); moreover, every edge of G is contained in at least two triangles;

(viii):

\(\theta (G) \ge \iota (G)\);

(ix):

the complement \(\overline{G}\) of G is connected;

(x):

there exists an induced \(P_4\) in G;

(xi):

\(\theta (G) \ge 4\);

(xii):

if \(\theta (G) = 4\), then for each vertex set P inducing a \(P_4\) and for each \(x \notin P\), P contains at most one vertex nonadjacent to x;

(xiii):

if \(\theta (G) = 4\), then any two vertices of any induced \(P_4\) in G form a dominating set. (In particular, each edge of any induced \(P_4\) is dominating.)

Proof

1. (i)

   Suppose by way of contradiction that G is not critical. Then there exists a vertex x such that \(\theta (G-x)=\theta (G)\). Let us denote by X the set of all edges incident to x. In the graph \(H:=G-X\) any clique cover contains \(\{x\}\) and so \(\theta (H)=\theta (G-x)+1\). The edge set X can be extended to a spanning forest F and

   $$\begin{aligned}\theta (G-F)\ge \theta (G-X)=\theta (H)=\theta (G-x)+1=\theta (G)+1.\end{aligned}$$

   Here \(G-F\) is a removed graph, thus \(\theta _1(G)\ge \theta (G-F)>\theta (G)\), contradicting the assumption that G is exact.

2. (ii)

   Suppose by way of contradiction that \(\theta (G) = \alpha (G)\) holds. Taking \(x\in V(G)\) arbitrarily, and using both equality and criticality,

   $$\begin{aligned}\alpha (G-x) \le \theta (G-x)\le \theta (G)-1=\alpha (G)-1\end{aligned}$$

   Consequently, x is contained in every maximum independent set of the graph. As x is arbitrary, this implies that G is edgeless, the proof is established.

3. (iii)

   By way of contradiction, assume that G is perfect. Then, from the Weak Perfect Graph Theorem [10], we have \(\theta (G)=\alpha (G)\), contradicting (ii).

4. (iv)

   If \(bc\notin E\), then \(\varphi (b)\ne \varphi (c)\) obviously holds in every co-coloring. If \(bc\in E\), consider the edge set X consisting of the edge bc together with all edges incident to a. We extend X to a 1-selection S. Thus, in an arbitrary minimum co-coloring of \(G-S\), \(\{a\}\) will yield a singleton class, moreover, b and c cannot have the same co-color. But \(\theta (G-S)=\theta (G)\) as G is exact, hence each minimum co-coloring of \(G-S\) is a minimum co-coloring of G as well.

5. (v)

   There is at least one edge not incident with a, for otherwise G would be a star (with at least one edge) and we would have the contradiction \(\theta _1(G) = |V| > \theta (G)\). It follows that any minimum co-coloring of \(G-a\) contains a co-color class with more than one vertex; let b and c be two vertices in it. Applying (iv) for the vertex triple a, b, c, we obtain that \(G-a\) is not uniquely co-colorable.

6. (vi)

   It is a well-known (but nontrivial) fact proved in [11] that in a partitionable graph G, \(G-a\) is uniquely co-colorable for any a. So, we can apply (v).

7. (vii)

   Let \(\theta (G)=k\). By way of contradiction, suppose that an edge \(x_1x_2=e\in E(G)\) occurs in at most one triangle. Then the subgraph S with the edges containing \(x_1\) or \(x_2\) (or both) is quasi-unicyclic. Since G is exact, \(\theta (G-S)=\theta (G)\) holds; that is, \(G-S\) has some co-coloring \({\mathcal {C}}\) with k colors. According to the construction of S, \(x_1\) and \(x_2\) are isolated in \(G-S\), consequently they necessarily yield one-element co-color classes in \({\mathcal {C}}\). Moreover, within \(G[V-\{x_1, x_2\}]\), \({\mathcal {C}}\) has \(k-2\) classes that form cliques in G, too. But we may attach the clique consisting of \(x_1\) and \(x_2\), thus yielding a (\(k-1\))-co-coloring in G, a contradiction.

8. (viii)

   Let us take an inducing vertex set W in G with \(|W|=\iota (G)\). The set of edges induced by W forms a quasi-unicyclic subgraph, and it can be extended to a 1-selection f of G. If we delete all the edges of f from G, we obtain a 1-removed graph \(G_f\). Hence W will be independent in \(G_f\). Consequently,

   $$\begin{aligned}\theta (G) = \theta _1 (G) \ge \theta (G_f) \ge \alpha (G_f)\ge |W| = \iota (G).\end{aligned}$$
9. (ix)

   We know from (i) that G is critical, thus \(\overline{G}\) is chromatic critical. Consequently, \(\overline{G}\) is connected.

10. (x)

    A result of Seinsche [13] states that if for a graph G, having at least two vertices, both G and its complement are connected, then there exists an induced \(P_4\) in it.

11. (xi)

    The \(P_4\) guaranteed by (x) is an inducing subgraph. Thus, \(\iota (G)\ge 4\), and we are done by (viii).

12. (xii)

    If x has at most two neighbors in P, then \(P\cup \{x\}\) induces a quasi-unicyclic subgraph of order 5. By (viii) this would imply \(\theta (G)\ge \iota (G) \ge 5\), a contradiction.

13. (xiii)

    This is a direct consequence of (xii). \(\square \)

For example, if G is the complement of a cycle \(C_k=v_1v_2\dots v_k\), \(k>3\), then G is not exact. One explanation is that, for every i, the complement of \(G-v_i\) is a connected bipartite graph, thus it is uniquely 2-colorable, hence \(G-v_i\) is uniquely co-colorable; cf. (v). Another reason is that \(\theta (G)\le 3\), cf. (xi). In fact \(v_1\mapsto v_1v_4\), \(v_2\mapsto v_2v_4\), \(v_3\mapsto v_1v_3\) is a partial 1-selection verifying \(\iota (G)\ge 4\), cf. (viii).

3.3 Vertex Arboricity

Proposition 6

For every graph G the bounds \(a(G)/2 \le \chi _1(G) \le a(G)\) are valid and tight.

Proof

The upper bound follows directly from the definitions. Moreover it is tight because \(\chi _1(G) = 1 = a(G)\) holds whenever G is a tree. For arbitrarily large values of a(G), we refer to Example 2: a complete multipartite graph with any number k of vertex classes and more than k vertices in each class satisfies the equality \(\chi _1=\chi =k\), hence its vertex arboricity is also the same.

For the lower bound we use Proposition 1(i) and observe that the vertex set of each omitted cycle under an optimal edge-selecting function f can be partitioned into two paths, hence obtaining a coloring of G such that each color class induces a tree. Tightness is shown e.g. by any graph G in which each connected component is a cycle. Then we have \(\chi _1(G)=1\) and \(a(G)=2\).

We can give constructions \(G_k\) for general \(\chi _1=k\), too. Let \(V_1,\dots , V_k\) be mutually disjoint sets of size 3k each. Put a complete bipartite graph \(K_{3k,3k}\) between any two \(V_i,V_j\) and put k disjoint triangles inside each \(V_i\). We prove that this graph has \(a(G_k)=2k=2\chi _1(G_k)\).

Suppose that \(X_1\cup \cdots \cup X_a = V(G_k)\) is a vertex partition into \(a=a(G_k)\) classes, such that each \(X_\ell \) induces an acyclic subgraph. For a distinction, we call a \(V_i\) a part of G, and an \(X_\ell \) a class of G. No class can meet more than two parts, otherwise, it would induce at least one triangle. Hence we may have “single classes” entirely contained in a part, and “double classes” that meet two parts. We first consider the single classes.

If a part contains more than one single class, then we may assume without loss of generality that it is the union of exactly two single classes. We remove all those parts and classes, say \(k''\) parts and \(2k''\) classes. The remaining graph, say \(G'\), has \(k':=k-k''\) parts and vertex arboricity \(a':=a-2k''\). We need to prove that \(a'\ge 2k'\) holds. Let \(a'=s+d\), where s and d denote the number of single classes and the number of double classes, respectively. The size of a single class is at most 2k, and there can be at most \(k'\) of them; while the size of a double class is at most \(k+1\), because it can meet one of the two parts in just one vertex (in order to avoid a \(C_4\)) and can contain at most one vertex from each triangle of the other part. Since all of the \(3kk'\) vertices must be covered, we obtain

that means \(a'\ge 2k'\) as \(a'\) is an integer. \(\square \)

3.4 Vertex Degrees

Theorem 7

(Maximum degree) Let k be any positive integer. If \(\Delta (G) < 3k\), then \(\chi _1(G)\le k\); that is, \(\chi _1(G) \le \Big \lceil \frac{\Delta (G)+1}{3} \Big \rceil \). Moreover, the bounds are tight for both \(\Delta \) and \(\chi _1\) as there exist graphs \(G_k\) with \(\Delta (G_k)=3k\) and \(\chi _1(G_k)=k+1\).

Proof

Beginning with the assertion on tightness, the complete graphs \(G_k=K_{3k+1}\) are suitable examples.

For the assertion on \(\chi _1\), let \(G=(V,E)\) be a graph with maximum degree at most \(3k-1\). We take a vertex partition \((V_1,\dots ,V_k)\) of G such that the total number of edges joining distinct classes \(V_i,V_j\) (\(1\le i<j\le k\)) is as large as possible. Then each class induces a subgraph of maximum degree at most 2. Indeed, if \(v\in V_i\) has at least three neighbors inside \(V_i\), then at most \(3k-4\) edges join v to the other \(k-1\) classes, hence there is a class \(V_j\) in which v has at most two neighbors. Re-defining then \(V_i:=V_i{\setminus }\{v\}\) and \(V_j:=V_j\cup \{v\}\) we obtain a partition with more crossing edges, a contradiction. It follows that each class induces a union of paths and cycles, therefore a 1-selection can contain all edges inside the k classes, thus \(\chi _1(G)\le k\). \(\square \)

Theorem 8

(Degeneracy) Every d-degenerate graph G has \(\chi _1(G) \le d/2 + 1\). Moreover, this upper bound is tight as for every \(k\ge 1\) there exists a graph \(H_k\) such that \(H_k\) is 2k-degenerate and \(\chi _1(H_k)=k+1\).

Proof

Consider a graph G with degeneracy number d. Let \(v_1,v_2,\dots ,v_n\) be an enumeration of the vertices of G such that every \(v_i\) has at most d neighbors in \(\{v_j:j<i\}\). We define a 1-selection \(f:V(G)\rightarrow E(G)\) and a coloring \(c:V(G)\rightarrow \{1,2,\dots , \lfloor d/2\rfloor +1\}\) simultaneously. We let \(c(v_1)=1\) and \(f(v_1)\) an arbitrary edge of G incident to \(v_1\). Suppose we have defined c and f for all vertices \(v_1,\dots ,v_i\) such that c is a proper coloring of \(G[v_1,\dots ,v_i]_f\). Then as \(v_{i+1}\) has at most d neighbors in \(v_1,\dots ,v_i\), there must exist a color class \(c^{-1}(j)\) for some \(j\le \lfloor d/2\rfloor +1\) such that \(v_{i+1}\) has at most one neighbor in \(c^{-1}(j)\). We then let \(c(v_{i+1})=j\) and define \(f(v_{i+1})\) to be the edge joining \(v_{i+1}\) to its only neighbor in \(c^{-1}(j)\) (if it exists, otherwise \(f(v_{i+1})\) can be an arbitrary edge incident to \(v_{i+1}\)). Clearly, once c and f are defined on the entire graph, c is a proper coloring of \(G_f\). This finishes the proof of the upper bound \(d/2+1\).

Tightness for \(d=2\), that is \(k=1\), is clear by \(H_1:=K_4-e\). A general construction will have vertex set \(V=V(H_k)=V_0\cup V_1\cup \cdots \cup V_{k'}\) where \(k'=\lceil (2k+1)/3 \rceil \) will suffice. The subgraph induced by \(V_0\) is \(K_{2k}\). For each \(1\le i\le k'\) the set \(V_i\) is independent and has size \((k+1)\cdot \left( {\begin{array}{c}|V_0|+\ldots +|V_{i-1}|\\ 2k\end{array}}\right) \). Each \(v\in V_i\) has 2k neighbors in \(\bigcup _{j=0}^{i-1} V_j\), and any 2k vertices of \(\bigcup _{j=0}^{i-1} V_j\) have \(k+1\) common neighbors in \(V_i\). This graph \(H_k\) clearly has degeneracy number 2k, and so the first part of the theorem guarantees \(\chi _1(H_k)\le k+1\).

Suppose for a contradiction that \(\chi _1(H_k)\le k\), and let \(V=X_1\cup \cdots \cup X_k\) be a vertex partition where each \(X_j\) induces a quasi-unicyclic graph. Observe that \(K_4^-:=K_4-e\) is not quasi-unicyclic. For an \(i\ge 0\) let us write \(c_i=|\{j:X_j\cap (\cup _{h=0}^iV_h)\ne \emptyset \}|\) and \(p_i=|\{j:H_k[X_j\cap (\cup _{h=0}^iV_h)]\) contains an edge\(\}|\). As \(K_k[V_0]\) is complete, we have \(c_0+p_0\ge \lceil \frac{4k}{3}\rfloor \) and \(c_0\ge \lceil \frac{2k}{3}\rceil \). We claim that as long as \(p_i<k\), we have \(c_i+p_i<c_{i+1}+p_{i+1}\). Indeed, consider a set \(D\subseteq \cup _{h=0}^iV_h\) that contains an edge in all \(p_i\) possible colors and a vertex from all possible \(c_i\) color classes. There exists a set N of \(k+1\) vertices in \(V_{i+1}\) that are joined to all vertices of D. As \(K_4^-\) is not quasi-unicyclic, N can contain at most one vertex from each color class with an edge in D. As \(p_i<k\), there exists a vertex \(x\in N\) that is not of these colors. If its color class is completely new, then \(c_{i+1}>c_i\) increases; and if it appears before, so in D, then \(p_{i+1}>p_i\). As \(c_i\le k\) for all i, \(c_0+p_0\ge \lceil \frac{4k}{3}\rfloor \) and \(c_0\ge \lceil \frac{2k}{3}\rceil \) imply \(p_i=k\) for some \(i\le \frac{2k}{3}\).

Finally, we claim that if \(p_i=k\), then the color classes \(X_1,X_2,\dots ,X_k\) cannot be extended to \(V_{i+1}\). To see this, consider again a set \(D'\) of 2k vertices that contains an edge from each color in \(\cup _{h=0}^iV_i\), and let \(N'\) be its joined neighborhood of \(k+1\) vertices in \(V_{i+1}\). By the pigeon-hole principle there exist two vertices x, y in the same color class, say in \(X_1\). Then together with the edge e in \(D\cap X_1\), they form a \(K_4^-\) in \(X_1\), contradicting the fact that \(H_k[X_1]\) is quasi-unicyclic. \(\square \)

3.4.1 Consequences for Planar and Outerplanar Graphs

In this extremely short subsection, we derive two consequences on planar graphs, whose coloring properties are among the most classical issues in graph theory.

Theorem 9

1. (i)

   If G is an outerplanar graph, then \(\chi _1(G)\le 2\).

2. (ii)

   If G is a planar graph, then \(\chi _1(G)\le 3\).

Proof

Both parts are consequences of Theorem 8. Every outerplanar graph is 2-degenerate, hence (i) follows by taking \(d(G)=2\). Moreover, every planar graph is 5-degenerate, hence (ii) follows by taking \(d(G)=5\). \(\square \)

Remark 1

Both parts of the theorem are tight. Clearly, every outerplanar graph G with n vertices and more than n edges has \(\chi _1(G)=2\), and maximal outerplanar graphs of order n have \(2n-3\) edges. This yields a large class of graphs verifying the tightness of (i). Concerning the tightness of (ii), using a construction from [8], Voigt [15] pointed out that a planar graph G with \(\chi _1(G)=3\) on 92 vertices exists. Independently, Kardoš, Lužar, and Soták [7] developed a method to construct an infinite family of planar graphs with \(\chi _1(G)=3\).

3.5 Chromatic Index

Theorem 10

If \(\Delta (G)>1\), then \(\chi _1'(G)\le \chi '(G)-2\). Moreover,

All these bounds are tight.

Proof

To prove the upper bound \(\chi '(G)-2\) we consider an edge coloring \(\psi \) with \(\chi '(G)\) colors. Choose two color classes, say \(E_1\) and \(E_2\). Then in \(E_1\cup E_2\), each connected component is a path or a cycle, hence \(E_1\cup E_2\) can be made a 1-selection f. The restriction of \(\psi \) to \(E\setminus (E_1\cup E_2)\) properly edge-colors \(G_f\) with \(\chi '(G)-2\) colors. This also implies \(\chi _1'(G) \le \Delta (G)-1\) by Vizing’s theorem.

For the lower bound \(\delta (G) - 2\) we observe that removing at most |V(G)| edges makes the vertex degrees decrease by at most 2 on average. Thus, there remains a vertex with degree of at least \(\delta (G) - 2\), implying \(\chi '(G_f) \ge \delta (G)-2\) for every 1-selection f.

Regular graphs of type 1 have \(\delta (G)=\Delta (G)=\chi '(G)\), and every color class in an optimal edge coloring is a perfect matching. Hence the removal of two color classes decreases all of these parameters with exactly 2. Tightness of \(\chi _1'(G) \le \Delta (G) - 1\) is shown e.g. by complete graphs of odd order. \(\square \)

On the other hand, it has to be noted that there is no lower bound on \(\chi _1'(G)\) in terms of \(\Delta (G)\). This fact is shown by trees of any large maximum degree, which have \(\chi _1'=0\).

In the first part of this section we prove that it is hard to compute, and even to approximate, the robust chromatic number of a generic input graph. After that, we show how all the four parameters \(\alpha _1,\omega _1,\chi _1,\theta _1\) are computable in linear time on graphs of bounded treewidth.

For the NP-hardness result, we restate Theorem 3:

• For every natural number \(k\ge 3\), the Robust k-colorability problem is NP-complete. Moreover, Robust coloring is not approximable within \(O(|V|^{1/2-\varepsilon })\) for any real \(\varepsilon > 0\), unless P \(=\) NP.

Proof

We begin with the observation that Robust k-colorability is in the class NP. A certificate, that can be verified in polynomial time, is a vertex k-partition such that each class induces a quasi-unicyclic graph. Here k is not required to be fixed, it may also depend on the order of the input graph.

To prove the hardness results, we apply reduction from the corresponding problems on proper vertex colorings of graphs. As it is well known, for every \(k \ge 3\) it is NP-complete to decide whether a generic input graph is k-colorable. Now, for any \(G=(V,E)\) of order n, we substitute each vertex v of G with an independent set \(S_v\) of size \(n+1\); if two vertices \(v,w\in V\) are adjacent, the edge vw is enlarged to \(K_{n+1,n+1}\), otherwise no edges are drawn between the corresponding two \((n+1)\)-sets. In this way a graph \(G^+\) of order \(n(n+1)\) is obtained, and the transformation takes polynomial time. We claim:

The second equality is straightforward since G is a subgraph of \(G^+\), and on the other hand, every proper coloring of G can be enlarged in a natural way to a proper vertex coloring of \(G^+\) with the same number of colors.

To verify the first equality we observe that picking one vertex from each set \(S_v\) in all possible ways, we obtain \((n+1)^n\) distinct subgraphs isomorphic to G. Each edge is contained in \((n+1)^{n-2}\) of those subgraphs. Hence removing a 1-selection \(f(V(G^+))\) from \(G^+\) we can destroy no more than \(n(n+1)^{n-2}\) copies of G, consequently we still have \(G \subset (G^+ - f(V(G^+))\). Thus, \(\chi _1(G^+) \ge \chi (G) = \chi (G^+) \ge \chi _1(G^+)\). This implies equality and finishes the proof of NP-completeness.

To prove inapproximability, we cite Zuckerman’s important result [16] stating that \(\chi (G)\) is inapproximable within \(n^{1-\varepsilon }\). In our case \(n \approx \sqrt{|V(G^+)|}\) holds, which yields a multiplicative error tending to infinity faster than \(|V|^{1/2-\varepsilon }\) in the approximation of \(\chi _1(G^+)\) as \(n\rightarrow \infty \). \(\square \)

We now turn to the positive result. It requires a technical introduction before we state the theorem.

The treewidth of a graph G, denoted by \(\text {tw}(G)\), is equal to \(\min \left( \omega (H)-1\right) \), where the minimum is taken over all chordal graphs \(H \supseteq G\). From an algorithmic approach, treewidth equivalently is introduced via tree decompositions; we shall use a more specific kind of them as defined below. For the fundamentals of the theory on treewidth, we refer to [9] and chapters 7 and 11 of [4].

Given any graph \(G=(V,E)\), a nice tree decomposition \(\mathcal {T}\) of G consists of a rooted binary tree T whose nodes will be denoted by \(x_1,\dots ,x_k\), together with non-empty subsets \(V_1,\dots ,V_k\subset V\) where each node \(x_i\) is associated with the corresponding \(V_i\).

Two types of restrictions are put on the sets \(V_i\). One type with three conditions is related to G, namely

(i):

\(V_1 \cup \cdots \cup V_k = V\);

(ii):

if \(vw\in E\) then there is a node \(x_i\) where \(v,w\in V_i\);

(iii):

if \(v\in V_{i'}\) and \(v\in V_{i''}\) then also \(v\in V_i\) holds for all i such that \(x_i\) is an internal node of the unique \(x_{i'}\)–\(x_{i''}\) path in T.

In order to have a clear distinction between the two structures, we use the term “vertices” in the graph G and “nodes” in the host tree T of its tree decomposition.

The other type of restrictions categorize the nodes \(x_i\) in terms of their down-degree in T and associated set \(V_i\), as follows:

• a leaf node \(x_i\) has no children in T

• an introduce node \(x_i\) has one child \(v_{i'}\) in T, and its set \(V_i\) is obtained from \(V_{i'}\) by inserting just one vertex, i.e. \(V_i = V_{i'}\cup \{v\}\) for some \(v\in V{\setminus } V_{i'}\);

• a forget node \(x_i\) has also one child \(x_{i'}\) in T, but its set \(V_i\) is obtained from \(V_{i'}\) by omitting just one vertex, i.e. \(V_i = V_{i'}{\setminus }\{v\}\) for some \(v\in V_{i'}\);

• a join node \(x_i\) has two children \(x_{i'},x_{i''}\) in T, and all their sets are the same, i.e. \(V_i = V_{i'} = V_{i''}\).

The width of \(\mathcal {T}\) is \(\displaystyle \max _{1\le i\le k} \left( |V_i|-1\right) \). Theory proves that \(\text {tw}(G)\le t\) holds if and only if G admits a nice tree decomposition having width at most t, that is \(|V_i|\le t+1\) for all i. It is also known that in this case the number of nodes in the host tree T need not exceed 4|V|, hence it can be ensured to be linear in the order of G.

For later reference, we denote by \(V_r\) the subset of V associated with the root of T.

Theorem 11

For every positive integer t, the values of \(\alpha _1\), \(\omega _1\), \(\chi _1\), and \(\theta _1\) can be determined in linear time on graphs of treewidth at most t.

Proof

Let \(\mathcal {G}=\mathcal {G}_t\) be the class of graphs G with \(\text {tw}(G)\le t\), for a fixed positive integer t. Consider a generic input graph \(G=(V,E)\) from \(\mathcal {G}\). We take a nice tree decomposition \(\mathcal {T}=(T;V_1,\dots ,V_k)\) of width t and \(|V(T)|=O(|V|)\). A dynamic programming algorithm will be applied along a postorder traversal of T. For each node \(x_i\) of T a computational table \(\textsf{Tab}_i\) will be determined.

The indexing of rows in the tables will have two major parts. The first part gives information about the 1-selection under consideration; this part is analogous to all the four problems \(\alpha _1,\omega _1,\chi _1,\theta _1\). The second part is more problem-specific, as it will be detailed later.

For any \(V_i\), the components of the first part of row indexing are:

• a partial (possibly empty) 1-selection f of edges inside the subgraph \(G[V_i]\) induced by \(V_i\) in G;

• a partition \(V_i^+\cup V_i^- = V_i\);

• the subset \(V_i^+\subset V_i\) consists of those vertices for which it is assumed that a 1-selection has already been made, either inside \(V_i\) or with an edge whose other end is in the earlier (already forgotten) subgraph of G;

• the subset \(V_i^-\subset V_i\) of vertices for which it is assumed that no 1-selection has been made yet.

We note that \(V_r^+ = V_r\) can be assumed without loss of generality, but this is not the case at nodes different from the root.

Analogously to the concept of D(G, f) proposed in the Introduction, it is convenient to represent the 1-selection f inside \(V_i\) by a directed graph, where an arc (v, w) means that the edge vw of G is assigned to v by f. This information can be handled in the tables of the four node types as follows.

• If \(x_i\) is a leaf node, then every subset consisting of vertices non-isolated inside \(V_i\) has to be considered as a \(V_i^+\), and for each \(V_i^+\) all possible 1-selections have to be taken in the indexing of rows of the table for \(x_i\).

• If \(x_i\) is an introduce node with child \(x_{i'}\), and the new vertex in \(V_i\) is v, then: the option \(v\in V_i^-\) has to be taken with all cases of \(V_{i'}\); and if v has at least one neighbor in \(V_{i'}\), then also \(v\in V_i^+\) has to be considered with every possible 1-selection at v. Moreover, for the subset of vertices \(v'\in V_{i'}^-\) that are adjacent to v, all combinations of edges for a 1-selection have to be taken; the corresponding vertices are then moved from \(V_i^-\) to \(V_i^+\).

• If \(x_i\) is a forget node, then the “forgotten” vertex is just removed from \(V_{i'}\), the status of the remaining vertices and 1-selection inside \(V_i\), is unchanged.

• If \(x_i\) is a join node, then it is necessary to check that the cases at \(V_{i'}\) and \(V_{i''}\) are compatible. This means not only that we have the same 1-selection f and the same partition (i.e., \(V_{i'}^-=V_{i''}^-=V_i^-\) and \(V_{i'}^+=V_{i''}^+=V_i^+\)) at the two children. If a vertex is in \(V_i^+\), then its selected edge must be inside \(V_i\).

In the recursive computation of parameters, all the subgraphs obtained by deleting the 1-selections will be considered.

\(\underline{\hbox {Computing }\omega _1:}\)

A complete subgraph after the removal of a 1-selection is complete also in G, and its vertices appear together in at least one \(V_i\). So in each \(V_i\) we register all possible complete subgraphs \(K\subset G_f[V_i]\) for every f and every \((V_i^-,V_i^+)\), and compute a value w(K).

At a leaf node, w(K) is the number |V(K)| of vertices in K.

At an introduce node with \(V_i=V_{i'}\cup \{v\}\), w(K) taken from the table of \(V_{i'}\) is unchanged if \(v\notin V(K)\), and otherwise it is \(w(K) = \max \left( w(K-v), |V(K)| \right) \).

At a forget node with \(V_i=V_{i'}{\setminus } \{v\}\), w(K) is redefined as the maximum of its former value at \(x_{i'}\) and that of \(w(K\cup \{v\})\).

At a join node, values w(K) are available in the tables of its two children. Then the updated w(K) is the larger of the two.

Then \(\omega _1(G)\) can be read from the root as follows: for every partial 1-selection f in \(G[V_r]\), one takes the maximum over all the w-values in rows corresponding to cliques \(K\subseteq G[V_r]_f\), and then one takes the minimum over all fs.

\(\underline{\hbox {Computing}\, \alpha _1:}\)

This algorithm is essentially the same as the one determining the independence number on graphs of bounded treewidth. The difference is that the possible removals of 1-selections have to be taken into account, and the independent sets of those subgraphs are listed.

At a leaf node, all independent sets S are listed, and the value is \(w(S)=|S|\).

At an introduce node with \(V_i=V_{i'}\cup \{v\}\), the value w(S) remains unchanged if \(v\notin S\), and it is computed as \(w(S):=w(S-v)+1\) if \(v\in S\).

At a forget node with \(V_i=V_{i'}{\setminus } \{v\}\), the formula \(w(S):=\max \left( w(S), w(S-v) \right) \) is applied.

At a join node, the value w(S) is computed as the sum of the two w(S) values at the children, minus |S|.

In the end, \(\chi _1(G)\) is equal to the largest value of \(w(S)=w(S,f)\) at the root of T, taken over all partial 1-selections f in \(G[V_r]\) and all independent sets \(S\subseteq G[V_r]_f\).

\(\underline{\hbox {Computing }\chi _1:}\)

Since \(\chi _1(G)\le \chi (G)\le \text {tw}(G)+1\) holds for every graph G, we know that \(\chi _1\) is bounded above by a constant. Then a simple linear-time algorithm to test whether \(\chi _1(G)\le k\) holds is obtained by generating all proper k-colorings of \(V_i\) with respect to f, and checking which of them is compatible (also regarding the partition \((V_i^+,V_i^-)\)) with at least one such coloring at each child node of \(x_i\).

In the end, \(\chi _1(G)\) is equal to the smallest k for which the algorithm above terminates with an admissible coloring at the root node.

\(\underline{\hbox {Computing }\theta _1:}\)

Here at each node \(x_i\) for each f and each \((V_i^+,V_i^-)\) we need to generate all partitions \(\mathcal {P}\) of \(V_i\) such that each partition class is a complete subgraph after the removal of the edges selected by f. Moreover, it is necessary to distinguish between two possibilities for each complete subgraph selected as a class in \(\mathcal {P}\). Namely, whether it is assumed to contain an already “forgotten” vertex in the computation or it did not have any vertex outside \(V_i\) previously.

At a leaf node, no class is associated with forgotten vertices, and the value \(w(\mathcal {P})\) of \(\mathcal {P}\) is the number of its classes.

At an introduce node with \(V_i=V_{i'}\cup \{v\}\), attaching v to a class of \(V_{i'}\) is feasible only if no forgotten vertices are associated with that class. If v is attached to an existing class, then \(w(\mathcal {P})\) remains the same as \(w(\mathcal {P}-v)\) in \(V_{i'}\); otherwise, if \(\{v\}\) is a new singleton class, then \(w(\mathcal {P})=w(\mathcal {P}-v)+1\).

At a forget node with \(V_i=V_{i'}{\setminus } \{v\}\), the value of a partition does not change; but the status of the class from which v has been removed will indicate from then on that it is associated with a forgotten vertex.

At a join node \(x_i\), it is not allowed to keep a partition \(\mathcal {P}\) if it has a class with associated forgotten vertices at both children of \(x_i\). (Apart from this condition, both children may associate forgotten vertices with any number of partition classes.) If a partition \(\mathcal {P}\) is kept for \(V_i\), then its value is the sum of values at the two children of \(x_i\), minus the number of classes in \(\mathcal {P}\).

At the end, \(\theta _1(G)\) is equal to the smallest value of \(w(\mathcal {P})=w(\mathcal {P},f)\) at the root of T, taken over all partial 1-selections f in \(G[V_r]\), where \(\mathcal {P}\) is the trivial partition with \(V_r^+ = V_r\). \(\square \)

This paper presents a systematic study of a new graphical invariant called the robust chromatic number, motivated by its applicability in extremal combinatorics. In addition, we introduce “robust versions” of several fundamental graph parameters, including the independence number, clique number, clique covering number, and chromatic index. Basic estimates and relationships to other parameters are established, and algorithmic aspects are also considered to some extent. While some of the new results parallel classical ones, others are distinct and unique.

One can naturally extend the robust version of any other graph invariant following the same approach used to obtain \(\chi _1\) from \(\chi \) or \(\omega _1\) from \(\omega \), etc. This opens up a promising new area for future research. Although we do not provide an explicit list of parameters here, we propose and encourage a systematic exploration of this aspect. In particular, any variant of graph coloring presents an interesting direction for further investigation.

Besides these very general suggestions, we list here some more definite problems that remain open in connection with the robust chromatic number. The first question concerns a possible strengthening in part (ii) of Theorem 9.

Problem 1

Do there exist planar graphs with \(\chi _1(G)=3\), or is 2 a universal upper bound?

It is a well-known elementary fact that the chromatic number is additive with respect to the complete join operation. This is not the case for \(\chi _1\), as shown by many examples above.

Problem 2

1. (i)

   Is there a transparent way to determine \(\chi _1(G \oplus H)\), at least if \(\chi _1(G)\) and \(\chi _1(H)\) are also given, possibly with optimal 1-selections \(f_G\) and \(f_H\) ?

2. (ii)

   Is there a natural graph operation for which \(\chi _1\) is additive on vertex-disjoint graphs?

3. (iii)

   Is there a natural analogue of the class of cographs (\(=\) the graphs not containing any induced \(P_4\) subgraph) for \(\chi _1\) ?

There seems to be a lot to do in strengthening the estimates in part (iv) of Theorem 5 for the union of k graphs, where the currently available constructions are very limited.

Problem 3

1. (i)

   Find matching lower and upper bounds on the robust chromatic number of the union of k graphs.

2. (ii)

   Given two integers \(k,t\ge 2\), compare \(\chi _1(G_1\cup \cdots \cup G_k)\) with \(\prod _{i=1}^k \chi _1(G_i)\) under the assumption that each \(G_i\) has \(\chi _1(G_i)\ge t\).

The line graph operation seems to be of interest in its own right.

Problem 4

1. (i)

   Describe further infinite classes of graphs whose members G satisfy the equality \(\chi _1'(G)=\chi _1(L(G))\).

2. (ii)

   Does \(\chi _1'(G)\le \chi _1(L(G))\) hold for every graph G ?

So far very little is known about the complexity of determining the robust parameters of graphs.

Problem 5

1. (i)

   Describe classes of well-structured graphs on which \(\chi _1\) can be determined in polynomial time.

2. (ii)

   Describe classes of well-structured graphs on which the computation of \(\chi _1\) is NP-hard.

3. (iii)

   Study the analogous problems for the related graph invariants \(\omega _1\), etc., introduced above.

4. (iv)

   Describe conditions in terms of forbidden subgraphs and forbidden induced subgraphs, under which the computation of various robustness parameters becomes tractable.

Problem 6

Study the properties of robust total coloring and its parameter \(\chi _1''\).