1
$\begingroup$

Given a graph, what is the minimum number of matchings needed such that their union contains all the edges in the graph? Is it related to the degree of the graph?

$\endgroup$
  • $\begingroup$ "Is it related to the degree of the graph?" Clearly, as the number you're after is trivially greater than or equal to the maximum degree. That's not always enough, though, as for instance odd complete graphs require one more. $\endgroup$ – Arthur Oct 26 '18 at 5:40
3
$\begingroup$

In other words, you're asking about the minimum number of colors needed to color all the edges of a graph $G$ so that adjacent edges have different colors. That number is called the "edge chromatic number" or "chromatic index" of $G$, and is denoted by the symbol $\chi'(G)$.

By Vizing's theorem, $\Delta(G)\le\chi'(G)\le\Delta(G)+1$ where $\Delta(G)$ is the maximum degree of $G$. For example, $\chi'(K_n)=\Delta(K_n)=n-1$ for even $n$, while $\chi'(K_n)=\Delta(K_n)+1=n$ for odd $n\gt1$.

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