Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

On the wiki page for edge coloring says the following two things:

  1. "If the size of a maximum matching in a given graph is small, then many matchings will be needed in order to cover all of the edges of the graph. Expressed more formally, this reasoning implies that if a graph has m edges in total, and if at most β edges may belong to a maximum matching, then every edge coloring of the graph must use at least m/β different colors."
  2. "For a regular graph of degree $k$ that does not have a perfect matching, this lower bound can be used to show that at least $k + 1$ colors are needed."

Can anyone explain the second point?

It also says that a regular graph has a 1-factorization (decomposition into perfect matchings) if and only if it has chromatic index equal to $\Delta(G)$. I understand the forward direction (the decomposition gives you the colouring), but why is the reverse implication true?

share|improve this question

2 Answers 2

A regular graph of degree $k$ with $n$ vertices has $nk/2$ edges. A perfect matching has $n/2$ edges, so $(nk/2)\div(n/2)=k$ colors would suffice, if you could factor the graph into perfect matchings. If no perfect matching, you need more colours --- at least $k+1$.

share|improve this answer
    
Can you elaborate on the part about if no perfect matching exists? –  user104179 Nov 24 '13 at 4:57
    
If no perfect matching exists, then a maximal matching has $\beta\lt n/2$ edges, so (by paragraph 1 of the question) needs at least $m/\beta=(nk/2)/\beta\gt(nk/2)/(n/2)=k$ colors. –  Gerry Myerson Nov 24 '13 at 5:08
    
Ok, I understand that part. If you have time, could you look at the implication that if the chromatic index is $\Delta(G)$, then it has a 1-factorization please? –  user104179 Nov 24 '13 at 5:28
    
I don't know what $\Delta$ means. –  Gerry Myerson Nov 24 '13 at 5:29
    
Sorry, it is the maximum degree of any vertex of the graph. In this case it's just $k$. –  user104179 Nov 24 '13 at 5:34

Claim: Let $G$ be a $k$-regular graph. Then $G$ has a 1-factorization iff $G$ has a edge $k$-coloring.

Pf. => Let $F$ be a 1-factorization of $G$. For each perfect matching $M$ in $F$, assign to the edges in $M$ a distinct color $c_M$. Clearly this is an edge $k$-coloring of $G$.

<= Let $C$ be an edge $k$-coloring of $G$. For each color $c$ assigned by $C$, the edges colored $c$ by $C$ form a perfect matching in $G$. This gives $k$ perfect matchings that are edge disjoint, which is a 1-factorization of $G$. QED

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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