2
$\begingroup$

Prove that $\chi(G) \cdot \chi(\bar{G})\geq n$

$\chi(G)$: number of colors required for a graph $G$.

Here $\bar{G}$ is a graph that consists of all the edges that are not in $G$.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

Answer of your question is available here

$\endgroup$
2
  • 2
    $\begingroup$ Please summarize the proof here, so it won't get lost if the link breaks. $\endgroup$
    – vonbrand
    Apr 19, 2013 at 13:54
  • $\begingroup$ @vonbrand Hopefully I should make sure the link does not break. $\endgroup$
    – Jernej
    Apr 19, 2013 at 16:04

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