1
$\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$
  • $\begingroup$ The proof of Vizing's theorem is constructive; at least, the one I know is. $\endgroup$ – Patrick Stevens May 13 '16 at 10:42
  • $\begingroup$ @PatrickStevens i don't want the proof of Vizing's Theorem. I want an algorithm :) $\endgroup$ – Arman Malekzadeh May 13 '16 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$ – Patrick Stevens May 13 '16 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$ – Arman Malekzadeh May 13 '16 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$ – A.Sh May 13 '16 at 10:58
3
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.