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.



Highly asymmetric regular graph
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$]


