Consider any regular graph $G$ with order $n$ and size $E$ and maximum degree $\Delta$. Now, we give a $\Delta+1$ coloring to the vertices such that each vertex and its neighbors receive distinct colors.

Consider a color class of independent vertices in such a coloring. If we remove the color class, then do we have a regular subgraph with with maximum degree $\Delta-1$?

I think yes. It is easily seen to be true in the case of complete graphs. It can also be extended, I think, to graphs with $\Delta\ge\frac{n}{2}$, since each color class in such a coloring would have at most $2$ vertices. But, given any regular graph, is the claim true? Thanks beforehand.

  • $\begingroup$ Consider the Petersen graph. Have you tried finding a 4-coloring of its vertices with the property that you propose? $\endgroup$ – EGME Jun 28 at 14:55
  • $\begingroup$ @EGME thanks! I could not find as of now. So does it mean it does not exist? Also, will this be true if the regular graph be balanced complete multipartite? Or if the graph were 1-factorizable? $\endgroup$ – vidyarthi Jun 28 at 15:25
  • 1
    $\begingroup$ In general it will not be possible to find a $\Delta+1$ with the property you want ... I don’t think so ... for the property you want to hold you are essentially coloring the square graph of the graph you start out with, so there will be a lot more edges in there and complete graphs induced by a vertex and its neighbors. In the Petersen example, you need 10 colors, which is a lot more than 4. $\endgroup$ – EGME Jun 28 at 15:38
  • 1
    $\begingroup$ Petersen(5,1) is planar, so it has it has an edge decomposition into perfect matchings, but you also need 5 colors for that one. $K_{3,3}$ is complete bipartite and 3-regular, but you need 6 colors. $\endgroup$ – EGME Jun 28 at 15:49
  • 2
    $\begingroup$ This is clearly false. It is easy to create counter-examples: just created $\Delta+1$ independent sets that represent the color classes and add edges so that vertices have zero or at least two neighbors in some of these classes. $\endgroup$ – Aravind Jun 30 at 6:56

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.