# All even order 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.

• Does it serves as a counterexample? Commented May 14, 2019 at 2:13
• @Bullet51 thanks, yes it should serve as a counterexample. But, are there vertex transitive counterexamples? Commented May 14, 2019 at 5:28
• Possibly not. Commented May 14, 2019 at 6:12
• I thought Class1 meant edge colorable with $\Delta(G)$ colors? Why would any non-regular graph be edge colorable with $\delta(G)$ colors?
– bof
Commented May 14, 2019 at 7:24

## 1 Answer

A counterexample can be found by adjointing a tree to a class-2 graph with some edges removed.

• so this implies that every induced subgraph of a class 1 graph is class 1, that is the edge coloring class is a hereditary one, right Commented May 14, 2019 at 8:22
• No. Consider K5+pendant and $K_5$. Commented May 14, 2019 at 8:24
• Ok is at least every even induced subgraph hereditary? or, say independece induced(formed by deleting independent set of vertices) even subgraph? Commented May 14, 2019 at 8:28
• No. Change the K5 in the previous construction into Petersen. P.S. Comments are not suitable for chatting. Commented May 14, 2019 at 8:29
• got it! But, I believe, every induced even subgraph of a Class 1 graph has $\Delta-2$ 1-factors. Any counterexample to this? Sorry, if it is too chatty, but bear just this one time! Commented May 14, 2019 at 8:32