1
$\begingroup$

Let $G= (V,E)$ be a graph, and let $G'= (V',E')$ be a copy of $G$. That is, for each $v ∈ V$ there is a corresponding $v' ∈ V'$ and for each edge $(u,v)∈E$ there is a corresponding edge $(u',v')∈E'$. Construct a graph $G\widehat{}$ by drawing an edge from each $v∈V$ to its corresponding $v'∈V'$. Prove that $\chi (G\widehat{}) =\chi (G)$.

My work: I sketched a few graphs such that they could be colored using two color and drew $G$ and $G'$ for each. By construction it's apparent that $G\widehat{}$ could also be colored using two colors. But i'm having a hard time extending this to more than two colors and actually writing down a proof, as a picture doesn't really count as proof.

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

If I'm understanding your question correctly, the new graph $\hat{G}$ is just two copies of $G$ with the corresponding vertices connected right? If so, just think about permuting the colors on the second copy. Explicitly, say you colored $V$ with the colors $\{1, 2, \ldots k\}$. Then for $v'\in V'$, if the corresponding $v\in V$ has color $i$ color $v'$ with $i+1 \mod k$.

$\endgroup$
6
  • $\begingroup$ Yes that's correct. I understand what you're saying but how do I connect it to χ(Gˆ)? $\endgroup$
    – user140161
    Apr 15, 2019 at 18:14
  • 1
    $\begingroup$ Well you colored all the vertices in $\hat{G}$ with the same colors as $G$, so the chromatic numbers are the same. That is, if you colored $G$ with $\{ 1,2, \ldots k\}$ then the above explains how to color $\hat{G}$ with $\{ 1,2, \ldots k\}$ also. $\endgroup$
    – Edgar Jaramillo Rodriguez
    Apr 15, 2019 at 18:48
  • 2
    $\begingroup$ Note that (a) $\chi (G\widehat{})$ is at least $\chi(G)$ as there is a subgraph of $G\widehat{}$ isomorphic to $G$. Yet @Edgar Jaramillo Rodriguez gave a proper coloring of $G\widehat{}$ using only $\chi(G)$ colors, this implies that (b) $\chi (G\widehat{})$ is also no more than $\chi(G)$, so (a) and (b) together imply equality. $\endgroup$
    – Mike
    Apr 15, 2019 at 18:51
  • 1
    $\begingroup$ So $\chi(\hat{G}) \geq \chi(G)$ since every coloring of $G$ admits a coloring of $\hat{G}$ with the same number of colors. But at the same time $\chi(\hat{G}) \leq \chi(G)$ since any coloring of $\hat{G}$ contains a coloring of $G$ in its subgraph. So in fact $\chi(\hat{G}) =\chi(G)$ $\endgroup$
    – Edgar Jaramillo Rodriguez
    Apr 15, 2019 at 18:51
  • 1
    $\begingroup$ I can rewrite the first sentence of my last comment: Note that (a) $\chi (G\widehat{})$ is at least $\chi(G)$, as $G$ that is a subgraph of $\chi (G\widehat{})$ is at least $\chi(G)$. But getting back to "isomorphism", the graphs $G$ and $G'$ are [by definition of "isomorphic"], isomorphic to each other. $\endgroup$
    – Mike
    Apr 15, 2019 at 19:00

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.