1
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Consider the Petersen graph. Have you tried finding a 4-coloring of its vertices with the property that you propose? $\endgroup$
    – EGME
    Commented Jun 28, 2019 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
    Commented Jun 28, 2019 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
    Commented Jun 28, 2019 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
    Commented Jun 28, 2019 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
    Commented Jun 30, 2019 at 6:56

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .