8
$\begingroup$

$\chi'(G)$ being the chromatic index of $G$, $\chi(G)$ its chromatic number and $\Delta(G)$ its maximum degree.

Here's the solution that I'm given, but I don't understand it:

Apply Brooks' theorem to the line graph of G.

I see how $\chi'(G) = \chi(L(G))$.

But a graph G with $\Delta(G) = 3$ can obviously have a line graph such that $\Delta(L(G)) > 3$, take for example:

Graph whose line graph has a maximum degree greater than the graph itself Line graph of the graph

Additionally the line graph could turn out to be an odd cycle...

Any idea where to go from there?

$\endgroup$
0

2 Answers 2

5
$\begingroup$

You don't need to worry about odd cycles, because they can be colored with three colors and you are allowed four.

You need to justify three things:

  1. Show that the maximum possible degree is $4$ (not so bad, I think).
  2. Show that thine graph cannot be the complete graph on five vertices, i.e. that you will not get a clique (you can check by going backwards if you like).
  3. You don't care if you get an odd cycle.

The you can use Brook's theorem in all its glory.

For further information, this result is called Vizing's Theorem.

$\endgroup$
3
  • $\begingroup$ You probably meant that $K_5$ is the case to rule out, rather than $K_4$. $\endgroup$
    – Erick Wong
    May 31, 2013 at 1:32
  • $\begingroup$ @Erick: ah, yes. Thank you for that. $\endgroup$
    – davidlowryduda
    May 31, 2013 at 2:57
  • $\begingroup$ I don't think this easy special case is called Vizing's theorem. I think Vizing's theorem is the one that says $\chi'(G)\le\Delta(G)+1$ in general, and I recall the proof being more complicated than the one you gave. $\endgroup$
    – bof
    Mar 31, 2017 at 8:58
4
$\begingroup$

Suppose $\Delta(G) = 3$. We need to show that 4 colors suffice to color the edges of the graph.

Let $uv$ be an edge in $G$. How many edges share a common endpoint with this edge? Since $\Delta=3$, at most two other edges besides $uv$ are incident to the vertex $u$, and similarly for $v$. So, at most $2+2=4$ edges share a common endvertex with edge $uv$. Thus, in the line graph of $G$, the vertex $uv$ has degree at most 4. If this line graph $L(G)$ is not an odd cycle or a complete graph, by Brook's theorem its vertices (and hence the edges of $G$) can be 4-colored.

If the line graph is an odd-cycle, its vertices can be 2- or 3- colored, hence 4 colors suffice. If the line graph is the complete graph $K_r$, then consider the value of $r$. If $r=3$, this $K_3$ is the line graph of either $K_3$ or a star $K_{1,3}$, and in either case 3 colors suffice. If $r \ge 4$, then this $K_r$ arose from a $G$ that is necessarily a star $K_{1,r}$. (This is a basic result on line graphs: any clique in $L(G)$ containing 4 or more vertices is induced by a star in $G$.) Since $\Delta(G) =3$, this star has exactly 3 edges; thus $r=3$ and three colors suffice again.

In other words, there is no clique of size 4 or more in the line graph $L(G)$ if $\Delta(G)=3$. More generally, all cliques in $L(G)$ arise from either stars $K_{1,r}$ in $G$ (i.e. the set of edges of $G$ that share a common endvertex) or triangles in $G$.

$\endgroup$

You must log in to answer this question.

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