2
$\begingroup$

A proper $k$-edge-coloring for a graph like $G$ is coloring every $e \in E(G)$ with $k$ colors such that no two edges of the same color share a common vertex.

According to Vizing Theorem, for every simple graph like $G$, We have a proper edge-coloring of $G$ with $\delta(G)$ or $\delta(G)+1$ colors.

Now my question is :
Is there a simple algorithm for coloring every simple graph with $\delta(G)+1$ colors?

Note : This question was taken from the book "Graph Theory with Applications" written by Bondy & Murty.

Thanks in advance.

$\endgroup$
5
  • $\begingroup$ The proof of Vizing's theorem is constructive; at least, the one I know is. $\endgroup$ May 13, 2016 at 10:42
  • $\begingroup$ @PatrickStevens i don't want the proof of Vizing's Theorem. I want an algorithm :) $\endgroup$ May 13, 2016 at 10:43
  • $\begingroup$ But the proof of Vizing's theorem is an algorithm. The proof I know is of the form "Here is an algorithm; we prove that it works". $\endgroup$ May 13, 2016 at 10:44
  • $\begingroup$ @PatrickStevens The one that i know uses a lemma to prove it. would you please provide the algorithm as an answer so that i could accept it ? $\endgroup$ May 13, 2016 at 10:45
  • $\begingroup$ Here is a pdf I found with a couple well-placed google searches, it outlines an algorithm that lies somewhat closer to implementation than a purely mathematical constructive proof: cgi.csc.liv.ac.uk/~michele/TEACHING/COMP309/2003/vizing.pdf $\endgroup$
    – MonadBoy
    May 13, 2016 at 10:58

1 Answer 1

4
$\begingroup$

The algorithm is: pick an edge $x y_1$. Inductively find a $\Delta+1$ colouring $\phi$ of $G \setminus \{ x \to y_1 \}$.

For every vertex, there is a colour which is not used at that vertex, because the degree of the vertex is $\leq \Delta$ but we have $\Delta+1$ colours to choose from.

Let $c$ be a colour missing from vertex $x$, and $c_1$ missing from $y_1$. Then if $c_1$ is missing at $x$, we are done: colour the edge $x y_1$ with colour $c_1$.

Otherwise, $c_1$ is not missing at $x$, so there is some $y_2$ in the neighbourhood $\Gamma$ of $x$ with $\phi(x \to y_2) = c_1$.

Repeat: given $y_1, \dots, y_k \in \Gamma(x)$ distinct, and distinct colours $c_1, \dots, c_k$ such that $c_i$ is missing at $y_i$ for all $i$, and $\phi(x y_i) = c_{i-1}$, do the following: if $c_k$ is missing at $x$, stop and recolour $x y_i$ with colour $c_i$. Otherwise, let $y_{k+1} \in \Gamma(x)$ be such that $\phi(x y_{k+1}) = c_k$, and let $c_{k+1}$ be a colour missing at $y_{k+1}$.

This process builds a list of distinct $y_i$ and $c_i$, so eventually it must terminate: it can only terminate if we find $c_{k+1}$ which has already appeared as an earlier $c_i$. Wlog $c_1 = c_{k+1}$, because we can recolour $x y_j$ with colour $c_j$ for $1 \leq j \leq i-1$ and un-colour $x y_i$ itself.

Consider the subgraph of $G$ which is coloured only in colours $c_1, c$ (recalling that $c$ is the colour missing at $x$). The maximum degree of this subgraph is $2$, so its components are paths and cycles; but $x, y_1, y_{k+1}$ all have degree $1$ in this subgraph and so must not lie in the same component. If $x, y_1$ are disconnected in the subgraph, swap $c, c_1$ on the $c, c_1$-component of $y_1$, and let $\phi(x, y_1) = c$. Otherwise, $x, y_{k+1}$ are disconnected in the subgraph, so swap $c$ and $c_1$ on the $c, c_1$-component of $y_{k+1}$, and recolour $x y_{k+1}$ by $c$, $x y_i$ by $c_i$ for each $i \in [1, k]$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .