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 Answers 2

Reset to default
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, 2013 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$
    – Gerry Myerson
    Nov 24, 2013 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, 2013 at 5:28
  • $\begingroup$ I don't know what $\Delta$ means. $\endgroup$
    – Gerry Myerson
    Nov 24, 2013 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, 2013 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$

You must log in to answer this question.

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