2
$\begingroup$

Consider any graph with $n$ vertices and maximum degree $\Delta$. By Vizing's theorem, the graph could be edge colored(properly) with at most $\Delta+1$ colors.

My question pertains as to what the maximum and minimum number of 1-factors(independent edges) we could put in a color class. For regular Class $1$ graphs, the answer should be exactly $\frac{n}{2}$ edges. But, what for an arbitrary graph? What if the graph were regular(Class 2)? What if, in addition it were vertex transitive, or, even better, Cayley?

$\endgroup$
2
  • 2
    $\begingroup$ If the regular class 2 graph has a perfect matching, one can choose the matching to be one of the color class. $\endgroup$ Commented May 2, 2019 at 8:27
  • $\begingroup$ @Bullet51 so then, the question reduces to how many perfect matchings/maximum matchings there are in the graph, right? $\endgroup$
    – vidyarthi
    Commented May 2, 2019 at 10:13

0

You must log in to answer this question.

Browse other questions tagged .