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?

  • 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$ – Bullet51 May 2 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 May 2 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.