2
$\begingroup$

For the graph $D_n$ created from complete graph $K_n$ by replacing one of edges by path on 3 vertices.

For example, the graph attached is $D_4$. enter image description here

I can prove that the edge chromatic number is $n$. Now I do not know how to prove that if we delete any edge in $D_n$, then it is $n-1$ edge colorable.

$\endgroup$
  • $\begingroup$ Didn't you remove 2 edges in $D_4$? $\endgroup$ – Franck Dernoncourt Jan 24 '14 at 23:09
  • 1
    $\begingroup$ Another way to put it: $D_n$ is obtained from $K_n$ by adding a (degree two) vertex in the middle of one of the edges. $\endgroup$ – Hagen von Eitzen Jan 24 '14 at 23:11
  • $\begingroup$ Yes, Hagen's explanation is what I really mean. $\endgroup$ – Ginger Jan 24 '14 at 23:27
0
$\begingroup$

Seems I proved it by myself.

Theorem 1:: If $n$ is odd, then the chromatic index of complete graph $K_n$ is $n$; If $n$ is even, the chromatic index of $K_n$ is $n-1$.

Lemma 2: If we remove any edge in $D_d$, then the remaining graph is $d$-edge-colourable.

Proof: If we denote the vertices on $D_d$ by $1,2,\dots, d,d+1$ where vertices 1 and $d$ has degree $d-1$ and vertex $d+1$ has degree 2. Because of the symmetry, the edge being removed has 3 cases: 1. it is $(1,d+1)$ or $(d,d+1)$; 2. it is $(1,i)$ or $(d,i)$ where $i\in\{2,\dots, d-1\}$; 3. It is $(i,j)$ where $i,j\in\{2,\dots, d-1\}$.

From theorem1 we know that there is a $d$ edge coloring of $K_d$. And in $D_d$ we remove from $K_d$ the edge $(1,d)$ and add two edges $(1,d+1)$ and $(d,d+1)$. For the case 1, w.l.o.g. we assume that $(1,d+1)$ is removed, then we just color $(d,d+1)$ with the same color of $(1,d)$ in the edge coloring of $K_d$. It is a $n$ proper edge coloring of the remaining graph. For the case 2, w.l.o.g., we assume that $(1,2)$ is removed, then we color $(1,d+1)$ with the color of $(1,2)$ in $K_d$ and color $(d,d+1)$ with the color of $(1,d)$ in $K_d$, this constructs a proper edge coloring of the remaining graph. For the case 3, w.l.o.g., we assume we remove the edge $(2,3)$. Then we color $(d,d+1)$ with the color of $(1,d)$ in $K_d$. And the degree of vertex 1 in $K_d$ is $d-1$, so there is one color of $d$ which does not color any edge attaches to vertex 1, we use this color to color $(1,d)$. This is a proper edge coloring.

$\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.