0
$\begingroup$

It is a standard result, due to Fournier, that if the core of a graph (the induced graph by the vertices having their degrees equal to maximum degree of the graph) is a forest (acyclic), then the graph is Class 1 (edge colorable with colors equal to the maximum degree of the graph.

Is there a simple proof of this fact? Specifically, it is said that it follows from the Vizing Adjacency lemma. Any hints? Thanks beforehand.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Just reduce to a critical graph and apply the lemma to any leaf. $\endgroup$
    – Ilya Bogdanov
    Sep 5, 2019 at 5:54
  • $\begingroup$ @IlyaBogdanov could you elaborate a bit? I am not sure of the full statement of Vizing Adjacency Lemma except that if a graph is edge color critical, it should have $3$ major vertices $\endgroup$
    – vidyarthi
    Sep 5, 2019 at 5:56
  • 1
    $\begingroup$ I've googled it quickly;) see, e.g., Theorem 4 in faculty.math.illinois.edu/~kostochk/math581/viz4.pdf $\endgroup$
    – Ilya Bogdanov
    Sep 5, 2019 at 6:05
  • $\begingroup$ @IlyaBogdanov thanks! I wrote the answer now $\endgroup$
    – vidyarthi
    Sep 5, 2019 at 6:21

1 Answer 1

Reset to default
0
$\begingroup$

Thanks to the comment by @IlyaBogdanov, consider that the graph is not of Class 1, that is, its edge chromatic number is $\Delta+1$, where $\Delta$ be the maximum degree of the simple graph. Consider the minimal such graph, that is, a critical graph. Now, this should consist of only two major vertices connected by an edge.

Now, we apply the Vizing adjacency lemma (VAL) to one of the major vertex. This implies, by VAL that the vertex should have at least two major neighbours. But, it is adjacent to exactly one major neighbour, which is a contradiction. Continuing the process by adding leaves of major vertices (as trees can be formed this way), we obtain the full theorem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.