1
$\begingroup$

I tried to prove that if for a simple graph $G$, vertices of maximum degree induce a forest, then $\chi'(G) \leq \Delta(G)$, in other words, the graph is in Vizing Class 1.

When I applied induction on $|E(G)|$, I encountered the problem, that if there is only one vertex $v \in V(G)$ having maximum degree, I cannot ensure that I can apply the induction hypothesis on $G\setminus e$ for an edge $e$ incident with $v$.

If I remove $e$, there might be vertices of degree $\Delta(G) - 1$ inducing a cycle. This graph is an example. If we remove the degree 5 vertex, then the degree 4 vertices don't induce a forest.

How can I solve this problem? Is there a way to fix this proof?

$\endgroup$
5
  • $\begingroup$ Check this math.stackexchange.com/questions/1009600/… $\endgroup$
    – hbm
    Commented Nov 12, 2018 at 23:34
  • $\begingroup$ i tried to do the same, but i think there is a problem there. I can't apply the induction hypothesis, because $v$ might be the only vertex having maximum degree $\endgroup$
    – Lu K
    Commented Nov 13, 2018 at 1:15
  • $\begingroup$ the proof still applies. In the case of only one vertex, just remove any edge incident with it. $\endgroup$
    – hbm
    Commented Nov 13, 2018 at 1:30
  • $\begingroup$ i added an example now - i am worried that the induction hypothesis does not hold if i remove any edge incident with it $\endgroup$
    – Lu K
    Commented Nov 14, 2018 at 2:48
  • 1
    $\begingroup$ What you need is that, $G$ \ $e$ has a proper edge coloring with at most $\Delta(G)$ colors $\endgroup$
    – hbm
    Commented Nov 14, 2018 at 18:52

1 Answer 1

Reset to default
-1
$\begingroup$

if the maximum degree of G\e is not Δ(G),then Δ(G\e)+1≤Δ(G) and by Vizing there is a Δ(G) edge coloring. Thats all you need

$\endgroup$

You must log in to answer this question.

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