0
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – vidyarthi May 14 at 8:22
  • 1
    $\begingroup$ No. Consider K5+pendant and $K_5$. $\endgroup$ – Bullet51 May 14 at 8:24
  • $\begingroup$ Ok is at least every even induced subgraph hereditary? or, say independece induced(formed by deleting independent set of vertices) even subgraph? $\endgroup$ – vidyarthi May 14 at 8:28
  • 1
    $\begingroup$ No. Change the K5 in the previous construction into Petersen. P.S. Comments are not suitable for chatting. $\endgroup$ – Bullet51 May 14 at 8:29
  • $\begingroup$ 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! $\endgroup$ – vidyarthi May 14 at 8:32

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.