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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Does it serves as a counterexample? $\endgroup$
    – LeechLattice
    Commented May 14, 2019 at 2:13
  • $\begingroup$ @Bullet51 thanks, yes it should serve as a counterexample. But, are there vertex transitive counterexamples? $\endgroup$
    – vidyarthi
    Commented May 14, 2019 at 5:28
  • 1
    $\begingroup$ Possibly not. $\endgroup$
    – LeechLattice
    Commented May 14, 2019 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
    Commented May 14, 2019 at 7:24

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\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
    Commented May 14, 2019 at 8:22
  • 1
    $\begingroup$ No. Consider K5+pendant and $K_5$. $\endgroup$
    – LeechLattice
    Commented May 14, 2019 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
    Commented May 14, 2019 at 8:28
  • 1
    $\begingroup$ No. Change the K5 in the previous construction into Petersen. P.S. Comments are not suitable for chatting. $\endgroup$
    – LeechLattice
    Commented May 14, 2019 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
    Commented May 14, 2019 at 8:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .