3
$\begingroup$

Let $G_1$ and $G_2$ be $k_1$ and $k_2$ critical respectively. That is $\chi(G_1) = k_1$ and $\chi(G_2) = k_2$ and the removal of any vertex or edge reduces the chromatic number. I am trying to prove that the sum $G = G_1+G_2$ is $(k_1+k_2)$ critical. $G$ is the graph obtained by connecting every vertex in $G_1$ to every vertex in $G_2$.

Now it is clear that colouring $G$ by applying a proper $k_1$ coloring to $G_1$ and a proper $k_2$ coloring $G_2$ is the best we can do, so we have that $\chi(G) = k_1 + k_2$. It is also evident that removing an edge or vertex from either $G_1$ or $G_2$ would reduce the chromatic number since both graphs are critical. It remains to show that removing one of the edges between $G_1$ and $G_2$ also reduces the chromatic number. However, this is where I am stuck. I don't see how I may remove one such edge and obtain a proper $k_1 + k_2 -1$ coloring.

Any help would be appreciated:)

$\endgroup$
2
  • 1
    $\begingroup$ Out of curiosity, where did you encounter this result? I would expect that most standard texts would cover this. But I didn't find such a result anywhere. $\endgroup$
    – koifish
    Apr 20 at 13:42
  • 1
    $\begingroup$ It showed up in the notes from a course I'm following. I agree, I'm surprised I didn't find it anywhere else $\endgroup$
    – mNugget
    Apr 20 at 14:01

2 Answers 2

3
$\begingroup$

Let's say we remove an edge $xy$ with $x$ a vertex in $G_1$ and $y$ in $G_2$. Since $G_1$ is $k_1$ critical, we may choose a $k_1-1$ coloring on the graph $G_1'$ obtained by removing the vertex $x$. By the same argument, we choose a $k_2-1$ coloring on $G_2'$ obtained by removing the vertex $y$.

Then just pick a color that is neither in among the $k_1 - 1$ colors on $G_1'$ nor $k_2-1$ colors on $G_2'$ and assign it to both vertices $x$ and $y$. Since we removed the edge $xy$, we obtain this way a valid coloring which has $k_1+k_2-1$ colors.

$\endgroup$
3
$\begingroup$

I think it's something like this. Let $G_1$ and $G_2$ be the graphs respectively and $v \in V(G_1)$, $w \in (G_2$). Let $e = vw$, and say $e$ is the edge removed.

Consider $G_1 - v$, which by color criticality is $(k_1 - 1)$-colorable. Similarly, $G_2 - w$ is $(k_2 -1)$-colorable. Use $k_1 + k_2 - 2$ colors to color $(V(G_1) - v) \; \sqcup (V(G_2) - w)$ in the obvious way, and use the $(k_1 + k_2 - 1)$-th color to color $v$ and $w$. Now, in $(G_1 + G_2) \setminus e$, the only vertices with color $(k_1 + k_2 - 1)$ are $v$ and $w$, which happen to be non-adjacent.

$\endgroup$

You must log in to answer this question.

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