3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Can you elaborate on the part about if no perfect matching exists? $\endgroup$
    – user104179
    Nov 24 '13 at 4:57
  • $\begingroup$ 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. $\endgroup$ Nov 24 '13 at 5:08
  • $\begingroup$ 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? $\endgroup$
    – user104179
    Nov 24 '13 at 5:28
  • $\begingroup$ I don't know what $\Delta$ means. $\endgroup$ Nov 24 '13 at 5:29
  • $\begingroup$ Sorry, it is the maximum degree of any vertex of the graph. In this case it's just $k$. $\endgroup$
    – user104179
    Nov 24 '13 at 5:34
2
$\begingroup$

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

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