0
$\begingroup$

How can we prove that there exists a coloring of vertices for graph $G$ such that at least 2/9 fraction of all triangles in $G$ whose vertices have different colors?

  • 3
    Sorry, just did that, hope it is what you mean.2012-10-09

1 Answers 1

1

Color the graph randomly, the probability that a triangle whose vertices have different colors is $\frac{3 \times 2}{3 \times 3 \times 3}=\frac{2}{9}$. Let $X_{t}$ be the indicator random variable that $t$ has distinct colors, then $E[X_{t}]=\frac{2}{9}$. Let $T$ be the set of all triangles and $X=\sum_{t \in T}X_{t}$, by linearity of expectation, the expected number of triangles is $E[X]=\sum_{t \in T}E[X_{t}]=\frac{2}{9}|T|$. By probabilistic method, there exists a coloring that at least $\frac{2}{9}$ of triangles receive 3 distinct colors.

  • 0
    Thanks a lot. I updated the answer. Thanks for your time!2012-10-09