10
$\begingroup$

Looking to show that $\forall n \in \mathbb{N}$

$$\chi^{'}(K_{2n+2})=\chi^{'}(K_{2n+1})=2n+1$$

I'm trying to construct a colouring of the edges of $K_{2n+1}$ that leaves colour $i$ missing at vertex $i$ so I can move to $K_{2n+2}$ without increasing the index (for my induction) but the details of that initial colouring are hard to work out.

$\endgroup$
0

3 Answers 3

10
$\begingroup$

I agree with Leen that induction might not be the way to go. But still, most proofs on the colorability of $K_n$ do not construct an explicit coloring. I think it's worth it to construct one at least once, so here goes :)

Say your vertex set is $V = \{0, 1, \ldots, n - 1\}$ with $n$ odd.

Color the edge $\{i, j\}$ with color $i + j$ (mod $n$). You should be able to show that no vertex has two incident edges of the same color.

Now, one needs to show that each vertex in this coloring misses a distinct color. This'll show that $K_{n + 1}$ can be colored with $n$ colors, $n + 1$ being even.

Actually, vertex $i$ misses color $2i$ (mod $n$). For otherwise, there are distinct $i, j$ such that $i + j \equiv 2i$ (mod $n$). This implies that either $j = i$ or $j = n + i$, the two of which are not possible. All that remains for you to show is that for distinct $i, j$, $2i \not \equiv 2j$ (mod $n$), and hence that all vertices have a distinct color they're missing.

$\endgroup$
7
$\begingroup$

You probably should not use induction.

Vizing tells you that $\chi'(K_k)$ is either $k-1$ or $k$. If $\chi(K_k)=k-1$ every color appears at every vertex, so the edges of one color form a perfect matching, which implies that $k$ must be even.

You said you could handle the other part? (The other part is proved if you know, or can prove, that for odd $k$ $K_k$ has a decomposition in Hamiltonian cycles. Let me know if you don't know how to do this. It is not hard.)

$\endgroup$
7
  • $\begingroup$ I've been to all the lectures and I'm pretty sure Vizing's theorem is all we've got for edge colourings - in particular factors of a graph have not been defined $\endgroup$ Mar 2, 2015 at 16:05
  • $\begingroup$ One of the other questions I can't do though is about a 3-regular graph $G$ with $\chi^{'}(G)=3$ and a unique 3-edge colouring having exactly 3 Hamilton cycles which also seems close to the factorization idea, so I'll read into it $\endgroup$ Mar 2, 2015 at 16:07
  • $\begingroup$ The other direction is ok but I still have problems with this direction. For a start you have the index off by one in Vizing's theorem, but why "if there is a k-edge-coloring of $K_k$ every edge color must appear at each vertex"? $\endgroup$ Mar 2, 2015 at 18:12
  • $\begingroup$ I see that this would be true for a 1-factorisation with $\chi^{'}(K_k)$ factors but not for an optimal colouring (are these equivalent in general?) $\endgroup$ Mar 2, 2015 at 18:13
  • 1
    $\begingroup$ No, it does not just have to do with the 'degree of regularity'. So there are 3-regular graphs $G$ with $\chi'(G)=3$ (like $K_4$), but there are also 3-regular graphs that require 4 colors (like the Petersen graph). $\endgroup$ Mar 2, 2015 at 18:44
4
$\begingroup$

Just another solution: Label the vertices $1,2,\ldots, 2n+1$ and for each $i$, colour edge $(i+k,i-k)$ using colour $i$ for every $k=1,2,\ldots,n$ (operations modulo $2n+1$). This is a proper edge colouring using $2n+1$ colours with the property that no edge coloured $i$ is incident to vertex $i$.

Example for $2n+1=7$:

enter image description here

$\endgroup$
1
  • 2
    $\begingroup$ Actually it's the same colouring "pattern" as Manuel's answer, but with vertices relabelled. $\endgroup$
    – Casteels
    Mar 3, 2015 at 11:40

You must log in to answer this question.

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