Skip to main content
MathOverflow

Return to Question

added 21 characters in body
Source Link
vidyarthi
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22

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.

It is a standard result, due to Fournier, that if the core of a graph (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.

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.

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

If the core of a graph is a forest, then it is Class 1

It is a standard result, due to Fournier, that if the core of a graph (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.