Orientation and Coloring

593 Views Asked by At

Prove that the following two conclusion is equivalent for simple graph $G$.

(i) The chromatic number $\chi (G) \leq k$;

(ii) $G$ has an orientation where no directed path of length $k$ exists.

an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph.

Well, I have try my best to give much detail, but I don't have many thoughts about this problem. I'll count on you.

2

There are 2 best solutions below

1
On BEST ANSWER

(i) $\implies$ (ii): see Alex Ravsky's answer.

(ii) $\implies$ (i): Let $G$ be an oriented (finite) graph with no directed path of length $k.$ Let $H$ be a maximal acyclic subgraph of $G.$ For $v\in V(G)=V(H)$ let $f(v)$ be the length of a longest directed path in $H$ with initial vertex $v.$ Clearly the values $f(v)$ lie in $\{0,1,\dots,k-1\}.$ I claim that $f$ is a proper coloring of $G.$

Suppose $uv$ is a directed edge of $G;$ I have to show that $f(u)\ne f(v).$ There are two cases.

Case 1. $uv$ is an edge of $H.$ Since $H$ is acyclic, it's easy to see that $f(u)\gt f(v).$

Case 2. $uv$ is not an edge of $H.$ Since $H$ is a maximal acyclic subgraph of $G,$ this means that $H+uv$ contains a cycle; i.e., there is a path in $H$ from $v$ to $u.$ It follows that $f(v)\gt f(u).$

P.S. The argument above only works for finite graphs; the definition of $f(v)$ does not necessarily make sense in an infinite graph, as the maximum may not exist. Nevertheless, by the Erdős–De Bruijn theorem, the assertion is also true for infinite graphs, provided $k$ is finite.

2
On

Let $V$ be the set of vertices of the graph $G$.

$i\Rightarrow ii$. Let $r:V\to \{1,\dots,k\}$ be the coloring of $G$. Let $e=(v,u)$ be any edge of $G$. Then $r(v)\ne r(u)$ and we direct $e$ such that from the vertex colored in a smaller color to the vertex colored in a bigger color. Now we see that colors increasealong each directed path in $G$, so the lenght of the path cannot be bigger than $k-1$.