Let $G$ be a regular connected simple graph on $n$ vertices with chromatic number $\chi$ and maximum degree $\Delta$. Then, it is implied that $G$ is $\chi$-partite. Suppose, we remove one of the partite set of vertices. Then, what would be the maximum degree of the induced subgraph formed by the remaining vertices?

I may say with some confidence that the induced subgraph would have a maximum degree of $\textit{at least} $ $\chi-2$(as the remaining partite sets must be connected with each other, otherwise the graph would be disconnected). In addition, if the graph be vertex transitive, I think that the maximum degree of the induced subgraph would be $\Delta-1$. Any hints and counterexamples in this case? Thanks beforehand.

  • $\begingroup$ What about a 5-cycle? $\endgroup$ – Gordon Royle Jun 18 '19 at 13:55
  • $\begingroup$ @GordonRoyle yes, 5-cycle satisfies the criterion of having any induced subgraph(formed by removing ine part of independent vertices) having degree $\chi-2=3-2=$. I think this straight from the fact that $\chi\le\Delta+1$ for any graph(therefore the induced subgraph, which has $\chi-1$ as its chromatic number should have at least $\chi-2$ as the degree) $\endgroup$ – vidyarthi Jun 18 '19 at 16:03
  • $\begingroup$ @GordonRoyle by the way, if you meant that the $5$-cycle has a disconnected graph when one partite set is removed, then I agree on that point $\endgroup$ – vidyarthi Jun 18 '19 at 16:11
  • $\begingroup$ I don't understand your answer to Gordon. A $5$-cycle is vertex-transitive with $\Delta=2$ and $\chi=3$. If you remove a color class with a single vertex, the induced subgraph still has maximum degree $2$, so this is a counterexample. $\endgroup$ – verret Jun 18 '19 at 20:00
  • 1
    $\begingroup$ At the other end, if you take say a balanced multipartite graph (which is vertex-transitive), with $\chi$ parts of size $k$, then $\Delta=(\chi-1)k$, where one you delete a part, the maximum degree will be $(\chi-2)k$, so the difference can be arbitrarily large. $\endgroup$ – verret Jun 18 '19 at 20:04

Consider a complete $k$-partite graph $G$ where all parts have size $n/k >> k$. Then $\Delta = n(k-1)/k$, and even after removing a part the degree would still be $n(k-2)/k$ $=\Delta - n/k$. [I am not sure precisely what you mean by 'highly symmetric but you surely could remove some of the edges so that there are no graph automorphisms, the minimum degree stays high, and there remains in there a copy of a complete $k$-partite graph on $m >>k$ vertices so the chromatic number stays $k$]

| cite | improve this answer | |
  • $\begingroup$ yes, but what do you mean by "neither"? I mean, even in your example, the maximum degree of the induced subgraph formed by removing one part still satisfies $\Delta\ge\chi-2=k-2$ as $\frac{n(k-2)}{k}\ge\frac{n}{k}\ge k$ $\endgroup$ – vidyarthi Jun 18 '19 at 16:07
  • $\begingroup$ I didn't register the "at least" part before, my mistake $\endgroup$ – Mike Jun 18 '19 at 16:13
  • $\begingroup$ no problem, I just edited the question. $\endgroup$ – vidyarthi Jun 18 '19 at 16:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.