Vertex coloring a graph with a unique vertex of maximum degree

by Aidan   Last Updated September 11, 2019 18:20 PM - source

Suppose a graph $G$ has a unique vertex of maximum degree, and let $d_2$ be the second-highest degree in $G$. Show that $\chi(G)\leq d_2+1$.


I'm trying contrapositive and making some argument about partitioning into strictly more than $d_2+1$ independent sets, but I do not see how that points me toward a non-unique $\Delta$. Also since the problem does not specify connected I can't (and don't see how it relates anyway) use Brooks' theorem to obtain $\Delta$ as opposed to $\Delta+1$ for an upper bound.



Related Questions


Explain this proof of the 5-color theorem

Updated August 28, 2017 07:20 AM

5-color Theorem proof

Updated September 06, 2017 04:20 AM

Alternating path from any vertex to any vertex

Updated December 08, 2017 17:20 PM