Skip to main content
edited title
Link
bof
  • 13.4k
  • 2
  • 43
  • 66

All even order graphs with $\Delta\ge\frac{n}{2}$ is Class 1

Source Link
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22

All even graphs with $\Delta\ge\frac{n}{2}$ is Class 1

Are all even order graphs with maximum degree $\ge\frac{|V(G)|}{2}$ Class 1(edge-colorable(chromatic index) with $\delta(G)$ colors)? Here, $|V(G)|$ detnotes the number of vertices in the graph.

I think yes, because, by Erdos-Posa theorem on the number of maximal disjoint circuits in a graph, we have that any graph has a matching of size at least $min(\delta(G), \frac{|V(G)|}{2})$. Now, consider a regular graph of degree $\delta(G)$. Then, by the Erdós-Pósa theorem, it will have a perfect matching(as $\delta(G)\ge\frac{|V(G)|}{2})$, in fact, $\delta$ perfect matchings(I think), because each independence-induced subgraph(graph formed by deleting a set of independent vertices from the graph) would also have a 1-factor and thus, the whole graph should be 1-factorizable, that is must be Class 1. Thus, any graph with maximum degree at least $\delta(G)$ should be Class 1. Any hints. Thanks beforehand.