An orientation $\vec{G}$ of a graph $G$ is an assignment of an orientation (direction) to each edge. We call the directed edges arcs. So if the edge $vu$ is oriented from $v$ to $u$, we refer to the resulting directed edge as the arc $(v, u)$.
A colouring (or more specifically vertex colouring) of a graph $G$ is a labelling of the graph’s vertices with colours, drawn from the set of positive integers $\mathbb{Z}^+$, such that no two vertices sharing the same edge have the same colour. The minimum number of colours needed to colour a graph $G$ is called its chromatic number, and is often denoted by $\chi(G)$.
Now suppose that $\vec{G}$ is an acyclic orientation of the graph $G$. We will show that, if $k$ denotes the number of vertices in a longest directed path in $\vec{G}$, then $G$ is $k$-colourable.
To prove the above claim, we will simply devise a colouring of $\vec{G}$ where each vertex $v$ is coloured with a number $l$ which is equal to the number of vertices in any longest directed path that begins at $v$. Since the number of vertices in any longest directed path in $\vec{G}$ itself is $k$, it is quite obvious that this colouring uses exactly $k$ colours. So, all we need to do is to establish that it is indeed a valid $k$-colouring.
Let $v$ and $u$ be adjacent vertices of $G$, and suppose that the edge $vu$ is oriented as the arc $(v,u)$. Then, if the number of vertices in a longest path that originates at $u$ is $l$, the number
of vertices in a longest path that originates at $v$ has to be at least $l+1$. Thus, any 2 adjacent vertices $v$ and $u$ must have different colours in the described $k$-colouring, implying that it is valid.
We will also show that, if $G$ is a graph having chromatic number $k$, then there exists an acyclic orientation $\vec{G}$ of $G$ in which the longest directed path contains exactly $k$ vertices.
To prove the above claim, we will consider a colouring of $G$ with the colours $\{1, 2, …, k\}$, and devise an orientation $\vec{G}$ based upon these colours where we simply orient each edge from the vertex with lower label to the vertex with higher label. Since the magnitudes of the vertex colours strictly increase as we traverse any directed path in $\vec{G}$, we immediately conclude that there cannot be any directed cycles in $\vec{G}$. Moreover, since the total number of colours used is only $k$, we also conclude that any directed path in $\vec{G}$ can contain at most $k$ vertices. However, using the previous result, we already know that there has to be at least one directed path in $\vec{G}$ having at least $k$ vertices, because otherwise, the chromatic number of the graph $G$ would have been less than $k$. This completes the proof.
A colouring (or more specifically vertex colouring) of a graph $G$ is a labelling of the graph’s vertices with colours, drawn from the set of positive integers $\mathbb{Z}^+$, such that no two vertices sharing the same edge have the same colour. The minimum number of colours needed to colour a graph $G$ is called its chromatic number, and is often denoted by $\chi(G)$.
 |
| A vertex colouring of the Petersen graph with 3 colours, the minimum number possible. |
Now suppose that $\vec{G}$ is an acyclic orientation of the graph $G$. We will show that, if $k$ denotes the number of vertices in a longest directed path in $\vec{G}$, then $G$ is $k$-colourable.
To prove the above claim, we will simply devise a colouring of $\vec{G}$ where each vertex $v$ is coloured with a number $l$ which is equal to the number of vertices in any longest directed path that begins at $v$. Since the number of vertices in any longest directed path in $\vec{G}$ itself is $k$, it is quite obvious that this colouring uses exactly $k$ colours. So, all we need to do is to establish that it is indeed a valid $k$-colouring.
Let $v$ and $u$ be adjacent vertices of $G$, and suppose that the edge $vu$ is oriented as the arc $(v,u)$. Then, if the number of vertices in a longest path that originates at $u$ is $l$, the number
of vertices in a longest path that originates at $v$ has to be at least $l+1$. Thus, any 2 adjacent vertices $v$ and $u$ must have different colours in the described $k$-colouring, implying that it is valid.
We will also show that, if $G$ is a graph having chromatic number $k$, then there exists an acyclic orientation $\vec{G}$ of $G$ in which the longest directed path contains exactly $k$ vertices.
To prove the above claim, we will consider a colouring of $G$ with the colours $\{1, 2, …, k\}$, and devise an orientation $\vec{G}$ based upon these colours where we simply orient each edge from the vertex with lower label to the vertex with higher label. Since the magnitudes of the vertex colours strictly increase as we traverse any directed path in $\vec{G}$, we immediately conclude that there cannot be any directed cycles in $\vec{G}$. Moreover, since the total number of colours used is only $k$, we also conclude that any directed path in $\vec{G}$ can contain at most $k$ vertices. However, using the previous result, we already know that there has to be at least one directed path in $\vec{G}$ having at least $k$ vertices, because otherwise, the chromatic number of the graph $G$ would have been less than $k$. This completes the proof.
No comments:
Post a Comment