If $G=(V,E)$ is a simple, undirected graph, is there a regular graph $G_R$ such that $G$ is isomorphic to an induced subgraph of $G_R$ and $\chi(G) = \chi(G_R)$?

## 1 Answer

$\begingroup$
$\endgroup$

Yes, you can find such a $G_R$ of any degree greater than or equal to the maximum degree of $G$. This is the main theorem of the paper "On regular bipartite-preserving supergraphs" by G. Chartrand and C. E. Wall .