0
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ What about a 5-cycle? $\endgroup$ Jun 18, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 20:04

1 Answer 1

2
$\begingroup$

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$]

$\endgroup$
3
  • $\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, 2019 at 16:07
  • $\begingroup$ I didn't register the "at least" part before, my mistake $\endgroup$
    – Mike
    Jun 18, 2019 at 16:13
  • $\begingroup$ no problem, I just edited the question. $\endgroup$
    – vidyarthi
    Jun 18, 2019 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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