Suppose $G$ is a connected graph on $n$ vertices with $\Delta(G)= d\geq3$ and $G$ is not the complete graph on $d+1$ vertices. Then it is possible to delete at most $n/d$ edges so that the resulting subgraph is $(d-1)$-colorable.

I first proved that there exists a $d$-coloring of the graph in which color $d$ appears on vertices of degree $d$ (assuming that all degree $d$ vertices are mutually nonadjacent).

Secondly I proved that there exists a color say $\alpha$ which exists on at most $n/d$ vertices.

This can also be shown that every vertex of degree $d$ is adjacent to at least one vertex of color $\alpha$. Then I am trying to delete the edges between vertices of degree $d$ (of color $d$) and vertices of color $\alpha$ in such a way that by deleting at most $n/d$ edges, one reduces the degree of every vertex of color $d$ by at least $1$. But I am stuck with the case when two vertices of color $\alpha$ are adjacent to a common vertex of color $d$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.