4
$\begingroup$

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)$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

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 .

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .