Core of the graph $G_1\cup G_2$, where $G_1$ and $G_2$ are disjoint unions of complete graphs, is a complete graph

Question

Question
I'm looking for an answer to the following question from Hell and Nesetril's Graphs and Homomorphisms:

Let $G_1$ and $G_2$ be graphs such that $V = V(G_1) = V(G_2)$, and both $G_1$ and $G_2$ are disjoint unions of complete graphs (so each component of $G_i$ is complete). Let $G$ be the graph $(V, E(G_1)\cup E(G_2))$. Show that the core of $G$ is a complete graph.

---

Definitions
A retract from a graph $G$ onto a subgraph $H$ is a graph homomorphism that fixes $H$. I.e., For $H\leq G$, a retract is a map $f:G\rightarrow H$ such that $f(u) = u$ for $u\in V(H)$, and such that $uv\in E(G)$ implies $f(u)f(v) \in E(H)$. A core is a graph that does not retract onto any proper subgraph. The core of a graph $G$ is the unique-up-to-isomorphism subgraph of $G$ that is itself a core.

---

Commentary
It should be sufficient, and probably easier, to prove that the chromatic number of $G$ is equal to the size of the largest clique in $G$ (which in turn will be the size of the largest connected component of $G_1$ or $G_2$). So I'll be happy with any answer that shows $\chi(G) = \omega(G)$ instead.

I do not want an answer that makes use of a heavy literature result like the strong perfect graph theorem.

Answer 1

Consider the bipartite multigraph $H$ with:

• a vertex corresponding to each clique of $G_1$ on one side;
• a vertex corresponding to each clique of $G_2$ on the other side;
• for each $v \in V(G)$, an edge from the vertex representing $v$'s clique in $G_1$ to the vertex representing $v$'s clique in $G_2$.

By König's line coloring theorem, $H$ has an edge coloring with $\Delta(H)$ colors. This means $G$ has a vertex coloring with $\omega(G)$ colors. (The degree of a vertex in $H$ is the number of vertices in the corresponding clique of $G$.)

If you're uncertain about using König's line coloring theorem, we can prove it from Hall's theorem without too much effort. By adding dummy edges and vertices, we can make $H$ be $\Delta(H)$-regular. By applying Hall's theorem, we can find a perfect matching in the resulting multigraph; color the edges of that matching one color, remove them, and repeat on the $(\Delta(H)-1)$-regular multigraph remaining.