A note on orientation and chromatic number of graphs

Abstract

Let D be any edge orientation of a graph G. We denote by $\Delta _k(D)$ the maximum value t for which there exists a directed path $v_1, \ldots , v_k$ such that $d^{out}(v_k)=t$, where $d^{out}(v_k)$ is the out-degree of $v_k$ in D. We first obtain some bounds for the chromatic number of G in terms of $\Delta _k(D)$ and then show a relationship between $\Delta _k(D)$ and vertex partitions of a graph into degenerate subgraphs.

1 Introduction

All graphs in this paper are simple and undirected. By an orientation of a graph G we mean an edge orientation of G. Let D be an orientation of a graph G. Then D is said to be acyclic if it does not contain any directed cycle. The out-degree in D of a vertex v of G is the number of edges incident to v and directed out of v. The in-degree of v is defined similarly. Let S be any subset of vertices in G. We denote by G[S] the subgraph of G induced on S. Relationships between the chromatic number $\chi (G)$ and orientations of G have been studied widely in the literature. Perhaps the first result in this direction is a result by Gallai (1968), Roy (1967) and Vitaver (1962) (independent of each other) which asserts that if D is an orientation with longest path length $\ell (D)$, then $\chi (G)\le \ell (D)+1$. In fact it is easily observed that $\chi (G) = {\min }_D \ell (D)+1$, where the minimum is taken over all orientations of G. Moreover, if we restrict all orientations of G to acyclic ones then the same equality still holds. Deming (1979) obtained more results concerning acyclic orientations and chromatic number. Figueiredo et al. (2008) studied acyclic orientations with path constraints and obtained some interconnections with graph theoretical parameters such as chromatic and independence number. For other results concerning orientations and chromatic number we refer the reader to the book Jensen and Toft (1995). For any orientation D of G we denote by $\Delta ^{out}(D)$ the maximum out-degree in D. Some researchers have obtained upper bounds for chromatic and list chromatic number in terms of $\Delta ^{out}(D)$. It can be shown by the greedy coloring procedure that if D is acyclic then $\chi (G)\le \Delta ^{out}(D)+1$. An independent subset of vertices S is said to be a kernel for D if for each vertex $v\in V(G)\setminus S$, there is a directed edge vu in D such that $u\in S$. Richardson (1953) proved that if D has no odd directed cycle then D has a kernel. Using this fact Bondy, Boppana and Siegel noted (see Alon and Tarsi 1992) that Richardson’s theorem can be used directly to color the vertices of G using $\Delta ^{out}(D)+1$ colors in polynomial time. Alon and Tarsi extended this result to more general orientations Alon and Tarsi (1992). An Eulerian subgraph of D is a directed subgraph H such that the in-degree of every vertex in H is equal to its out-degree in H. By the size of an Eulerian subgraph H we mean the number of edges in H. A subgraph H of D is called “even” or “odd” according to the parity of |E(H)|. By an Alon-Tarsi orientation of a graph G we mean any orientation D of G, where the number of Eulerian spanning subgraphs of even size is different from the number of Eulerian spanning subgraphs of odd size. It was proved in Alon and Tarsi (1992) that $\chi (G)\le \Delta ^{out}(D)+1$ for any Alon-Tarsi orientation D of G.

In Zaker (2008) the author introduced a new parameter in terms of $\Delta ^{out}(D)$ as follows. Let D be any orientation of G. Denote by $\Delta _k(D)$ the maximum value t for which there exists a directed path $v_1, \ldots , v_k$ in D such that $d^{out}(v_k)=t$. It should be mentioned that if no such path exists, then $\Delta _k(D)$ is defined to be zero. The following theorem was proved in Zaker (2008).

Theorem 1

Let G be a graph and D any odd-cycle-free orientation of G. For any positive integer k, there is a greedy coloring of G (dependent on the orientation D) which uses at most $\Delta _k(D)+k$ colors.

2 Results

In the following theorem we prove that the bound of Theorem 1 is also true for Alon-Tarsi orientations.

Theorem 2

Let G be a graph and D any Alon-Tarsi orientation of G. Then for any positive integer k, $\chi (G) \le \Delta _k(D)+k$.

Proof

The proof is by induction on k. For $k=1$ we have $\Delta _1(D)=\Delta ^{out}(D)$, so the desired bound is originally proved in Alon and Tarsi (1992). Assume that the assertion holds for k. We prove it for $k+1$. Call a vertex v a tail if there exists a directed path $v_1 v_2 \ldots v_k$ in D such that $v=v_1$ and $d^{out}(v_k)\ge \Delta _{k+1}(D)+1$. Let T be the subset of G consisting of all tail vertices in D. Assume first that $T= \varnothing$. In this case there exists no tail in D and hence $\Delta _k(D)\le \Delta _{k+1}(D)$. By the induction hypothesis $\chi (G) \le \Delta _k(D)+k$. It follows that $\chi (G) \le \Delta _{k+1}(D)+k$, as desired. Assume now that $T\not = \varnothing$. Note that every vertex of T has zero in-degree in D. Otherwise we obtain a contradiction with the definition of $\Delta _{k+1}(D)$. It implies that T is an independent set in G. Now define $G'=G\setminus T$ and restrict the orientation D to the edges of $G'$ to obtain $D'$. Since no vertex of T has non-zero in-degree then $D'$ is an Alon-Tarsi orientation of $G'$. By the definition of T we have $\Delta _k(D')\le \Delta _{k+1}(D)$. By induction hypothesis we have

$$\begin{aligned} \chi (G')\le \Delta _k(D')+k \le \Delta _{k+1}(D) +k. \end{aligned}$$

Now $\chi (G)\le \chi (G')+1 \le \Delta _{k+1}(D) +k+1$ follows, since T is an independent set. This completes the proof. $\square$

Theorem 2 holds for Alon-Tarsi orientations. We will now consider orientations without any restrictions. The next theorem presents an upper bound for $\chi (G)$ in terms of $\Delta _k(D)$, where D is an arbitrary orientation. We need the concepts of degeneracy and coloring number of a graph G. The graph G is k-degenerate if its vertices can be ordered as $v_1, v_2, \ldots , v_n$ such that for each i the vertex $v_i$ has at most k neighbors among $\{v_1, \ldots , v_{i-1}\}$. The degeneracy of G is defined as the minimum value k such that G is k-degenerate. It has been shown that the degeneracy of G is equal to ${\max }_{H} \delta (H)$, where the maximum is taken over all subgraphs H of G and $\delta (H)$ stands for the minimum degree of H. Moreover, the coloring number of G is defined as $col(G)={\max }_{H}\delta (H)+1$. The degeneracy and coloring number of any graph can be determined in polynomial time (see e.g. Jensen and Toft 1995). It has been proved that $\chi (G)\le col(G)$.

Theorem 3

(i) For any orientation D of a graph G

$$\begin{aligned} \chi (G)\le 2\Delta _k(D)+k. \end{aligned}$$

(ii) For any positive integers t and k, there exist a graph G with an orientation D such that $\Delta _k(D)=t$ and $\chi (G)=2\Delta _k(D)+k$.

Proof

We prove part (i) by induction on k. First let $k=1$. In this case we show that $col(G)\le 2\Delta _1(D)+1$. Assume on the contrary that $col(G)\ge 2\Delta _1(D)+2$. Then there exists an induced subgraph H of G such that $\delta (H)\ge 2\Delta _1(D)+1$. Consider the edge orientation of H obtained by restricting D to the edges of H. Now, the following inequalities hold for any vertex v of H

$$\begin{aligned} 2\Delta _1(D)+1 \le d_H(v)=d^{in}_H(v)+d^{out}_H(v)\le d^{in}_H(v) + \Delta _ 1(D). \end{aligned}$$

It follows that $d^{in}_H(v)\ge \Delta _1(D)+1$ for any vertex v of H. We have also the following inequalities.

$$\begin{aligned} |H|(\Delta _1(D)+1) \le \sum d^{in}_H(v) = |E(H)| = \sum d^{out}_H(v) \le |H|(\Delta _1(D)). \end{aligned}$$

This contradiction proves the theorem for $k=1$. Assume that the assertion holds for k. We prove it for $k+1$. Similar to the proof of Theorem 2 by a tail vertex we mean any vertex v such that there exists a directed path $v_1 v_2 \ldots v_k$ in D such that $v=v_1$ and $d^{out}(v_k)\ge \Delta _{k+1}(D)+1$. Let T be the subset of G consisting of all tail vertices in D. Obviously no vertex of T has non-zero in-degree. In particular T is an independent set. Now consider $G'=G\setminus T$ and restrict the orientation D to $G'$ to obtain $D'$. By the definition of T we have $\Delta _k(D')\le \Delta _{k+1}(D)$. By induction hypothesis we have

$$\begin{aligned} \chi (G')\le 2\Delta _k(D')+k \le 2\Delta _{k+1}(D) +k. \end{aligned}$$

On the other hand, T is an independent set which implies $\chi (G)\le 2\Delta _{k+1}(D) +k+1$, as desired.

Now, we prove part (ii). Suppose that t and k are given. Let H be the complete graph on $2t+1$ vertices. The edge set of H is decomposed into t Hamilton cycles. We orient each Hamilton cycle in such a way that it forms a directed cycle. In the resulting orientation of H, each vertex has out-degree exactly t. Now we add $k-1$ extra vertices $v_1, v_2, \ldots , v_{k-1}$ to H. We form a complete graph on the vertex set $V(H)\cup \{v_1, \ldots , v_{k-1}\}$. We orient any edge of the form $e=vv_i$, where $v\in V(H)$ from $v_i$ to v. For any i and j with $1\le i<j \le k-1$, we orient the edge $v_iv_j$ from $v_i$ to $v_j$. Denote the resulting complete graph and orientation by G and D, respectively. It is clear that $\Delta _k(D)=t$. We have $\chi (G)=2t+k=2\Delta _k(D)+k$, as desired. $\square$

Theorem 3 gives another proof of the Gallai-Roy-Vitaver bound.

Corollary 1

For any orientation D of G, $\chi (G)\le \ell (D)+1$.

Proof

Let $k=\ell (D)+1$. Then $\Delta _k(D)=0$. Apply Theorem 3 for this k and obtain $\chi (G)\le \ell (D)+1$. $\square$

Acyclic orientations were studied widely in combinatorics from different aspects. Let G be a graph with n vertices, m edges and $\alpha$ acyclic orientations. In Barbosa and Szwarcfiter (1999) an algorithm is described for finding all acyclic orientations in overall time ${\mathcal {O}}(n+m)\alpha$. Let D be any acyclic orientation of G. We have $\chi (G)\le \Delta _k(D)+k$ Zaker (2008). In order to minimize the later upper bound over all acyclic orientations of G, we define the following notation

$$\begin{aligned} \delta _k^{out}(G):=\min _{D_{acyc}} \Delta _k(D) \end{aligned}$$

where the minimum is taken over all acyclic orientations D of G. The inequality $\chi (G)\le \delta _k^{out}(G)+k$ holds obviously. In the following, by a $(k_1, k_2, \ldots , k_t)$ -partition of a graph G we mean a partition $V(G)=V_1\cup \ldots \cup V_t$ such that $col(G[V_i])\le k_i$ for all $i=1, \ldots , t$. Vertex partition of general graphs and in particular planar graphs into degenerate subgraphs is the subject of much research. A strong result from Kawarabayashi and Thomassen (2009) asserts that a planar graph of girth at least five can be partitioned into an independent set and a forest. Theorem 4 shows a relationship between $\delta _k^{out}(G)$ and partitions of G into degenerate subgraphs.

Theorem 4

A graph G has $(1, \ldots , 1, t)$-partition, where the number of 1’s is $k-1$ if and only if $\delta _k^{out}(G)\le t-1$.

Proof

First, assume that $V_1, V_2, \ldots , V_k$ is a $(1, \ldots , 1, t)$-partition of G. We have $col(G[V_i])\le 1$ for each $i\le k-1$, so $V_i$ is an independent set for $i\le k-1$. Let $e=uv$ be any arbitrary edge of G. We orient the edge e according to the following cases.

Case 1. Either u or v does not belong to $V_k$. In this case without loss of generality there are i and j with $1\le i, j \le k$ such that $u\in V_i$ and $v\in V_j$. Now orient the edge e from u to v.

Case 2. Both u and v are in $V_k$. In this case $col(G[V_k])\le t$ because $G[V_k]$ is $(t-1)$-degenerate. Hence, the vertices of $G[V_k]$ can be ordered as $u_1, \ldots , u_p$ so that $u_j$ has at most $t-1$ neighbors in $G[u_1, \ldots , u_j]$ for each j. Now, there exist i and j with $1\le i < j \le p$ such that $u=u_i$ and $v=u_j$. Without loss of generality we may assume that $i<j$. We orient the edge e from v to u. Note that each vertex v has at most $t-1$ out-neighbors.

Denote the resulting orientation of the edges of G by D. By our construction of D, each directed path in D with k vertices necessarily finishes at $V_k$. Each vertex in $V_k$ has out-degree at most $t-1$. Hence $\Delta _k(D)\le t-1$. Therefore $\delta _k^{out}(G)\le t-1$. This proves one direction of the theorem.

Assume now that $\delta _k^{out}(G)\le t-1$. It follows that there exists an acyclic orientation D such that $\Delta _k(D)\le t-1$. Define $V_1$ as the set of vertices with in-degree zero in D. For each $i\le k-1$, define recursively $V_i$ as the set consisting of vertices having zero in-degree in $V(G)\setminus (\cup _{j=1}^{i-1} V_j)$. Finally let $V_k=V(G)\setminus (\cup _{j=1}^{k-1} V_j)$. Each $V_i$ is independent for each $i\le k-1$, hence $col(G[V_i])\le 1$. Corresponding to each vertex v in $V_k$ there exists a directed path $v_1, v_2, \ldots , v_{k-1}, v_k$, where $v_i\in V_i$ and $v_k=v$. We have $\Delta _k(D)\le t-1$. Hence each vertex of $G[V_k]$ has out-degree at most $t-1$ in D, so the degeneracy of $G[V_k]$ is at most $t-1$. We conclude that $col(G[V_k])\le t$ and that $V_1, \ldots , V_k$ is a $(1, \ldots , 1, t)$-partition for G. This completes the proof. $\square$

The final result concerns the computational complexity of determining $\delta _k^{out}(G)$. For any fixed k, the decision problem concerning $\delta _k^{out}(G)$ is as follows.

Instance: A graph G and an integer t.

Question: $\delta _k^{out}(G)\le t?$

In Yang and Yuan (2006) a graph G is called near-bipartite if V(G) can be decomposed into an independent subset and an acyclic subgraph. It was proved in Yang and Yuan (2006) that it is NP-complete to determine whether a given graph is near-bipartite. We also use the NP-completeness of k-colorability of graphs. Let $k\ge 3$ be any integer. It is NP-complete to decide if a given graph can be properly colored by k colors. For any graph G by $H=G\vee K_1$ we mean the graph obtained by adding a new vertex say u to G and putting an edge between u and each vertex of G.

Lemma 1

Let G be a graph and $k\ge 2$ any fixed integer. Set $H=G\vee K_1$. Then G is k-colorable if and only if $\delta _k^{out}(H)\le 1$.

Proof

Let v be the vertex added to G. Assume first that G is k-colorable and $V_1, \ldots , V_k$ is a partition of G into independent subsets. We make a partition for the vertices of H as follows. Set $U_i=V_i$ for each $i=1, \ldots , k-1$. Set also $U_k=V_k\cup \{v\}$. Note that $H[U_k]$ is a star graph and hence its coloring number is 2. Therefore, $U_1, \ldots , U_k$ is a $(1, \ldots , 1, 2)$-partition for H.

Assume now that $U_1, \ldots , U_k$ is a $(1, \ldots , 1, 2)$-partition for H. For the vertex v there are two possibilities.

Case 1. For some $i\le k-1$, $v\in U_i$. In this case it is clear that $U_i$ only contains the vertex v. Note that $U_k\subseteq V(G)$ and $H[U_k]=G[U_k]$ is acyclic. Hence we can partition $U_k$ into two independent subsets A and B. We observe that the sets $U_1, \ldots , U_{i-1}, U_{i+1}, \ldots , U_{k-1}, A, B$ introduce a partition of V(G) into k independent subsets. In other words G is k-colorable.

Case 2. $v\in U_k$. In this case $U_k\cap V(G)$ should be an independent set because $H[U_k]$ is acyclic. Hence $\{U_1, \ldots , U_k\cap V(G)\}$ is a partition of G into at most k independent sets. This completes the proof. $\square$

The next theorem proves that for any fixed $k\ge 2$, the related decision problem concerning $\delta _k^{out}(G)$ is NP-complete. Note that we can not use Lemma 1 to deduce NP-completeness of $\delta _2^{out}(G)$.

Theorem 5

Let k be any fixed integer. Then to determine $\delta _k^{out}(G)$ is NP-complete for $k\ge 2$ and has a polynomial time solution for $k=1$.

Proof

Theorem 4 shows that to determine $\delta _1^{out}(G)$ is equivalent to determining the coloring number (or degeneracy) of G. As we mentioned earlier this is a polynomial time task. Note first that for any fixed k, the decision problem corresponding to $\delta _k^{out}(G)$ is an NP problem. In fact an acyclic orientation D of G satisfying $\Delta _k(D)\le t$ is a short certificate for the problem. We show now that to determine $\delta _2^{out}(G)$ is NP-complete. For any graph G, $\delta _2^{out}(G)\le 1$ if and only if G admits a (1, 2)-partition. The later condition holds if and only if G is near-bipartite. We mentioned before Theorem 5 that the later problem is NP-complete. It follows that to decide whether $\delta _2^{out}(G)\le 1$ is an NP-complete problem.

To complete the proof we show that, given any graph G, to decide whether $\delta _k^{out}(G)\le 1$ is NP-complete for any fixed $k\ge 3$. Lemma 1 states that this problem is equivalent to k-colorability of G which is NP-complete. $\square$

We make a final remark that for bipartite graphs G, $\delta _2^{out}(G)=0$ but $\delta _1^{out}(G)$ may be arbitrarily large for bipartite graphs. It is an interesting problem to approximate $\delta _2^{out}(G)$ in polynomial time or obtain a suitable heuristic for this hard to compute parameter.