I have a clique of size 5 which is partially colored(black or white). I have to color remaining edges so that each of the triangle has either 1 or 3 black edges. How should I go about coloring the graph or how can I tell this is not possible.

  • $\begingroup$ If the clique was completely white, then it is not possible. $\endgroup$
    – Calvin Lin
    Sep 26 '13 at 15:09
  • $\begingroup$ @CalvinLin Is this the only case? When we see a completely white triangle then also we can say that this is not possible.What about how to go about coloring the graph if it is possible. $\endgroup$ Sep 26 '13 at 15:12

Ket $K_n$ be the complete graph with $n\geq3$ vertices (there is nothing special with $n=5$). A black-and-white coloring of its edges is admissible if all triangles have $1$ or $3$ black edges.

When a partial edge-coloring of $K_n$ is given denote by $\Gamma$ the subgraph of $K_n$ consisting of all $n$ vertices and the colored edges.

Theorem. (i) A partial edge-coloring of $K_n$ can be extended to an admissible full coloring iff $\Gamma$ contains no bad cycle, i.e., a cycle with an odd number of white edges. (ii) When $\Gamma$ contains no bad cycle the extension can be done in $2^{b_0-1}$ ways, where $b_0$ is the number of connected components of $\Gamma$.

Proof. An admissible coloring cannot have a bad cycle: If there were such a cycle there would be a shortest one, $$\gamma:=\{v_0,v_1,v_2,\ldots,v_r,v_0\}\ .$$ Since the coloring is admissible the triangle $\{v_0,v_1,v_2,v_0\}$ is a good cycle, and it is then easy to see that $\gamma':=\{v_0,v_2,\ldots,v_r,v_0\}$ is a bad cycle shorter than $\gamma$.

This shows that the condition formulated in (i) is necessary.

To prove the sufficiency we consider the given partial black-and-white edge-coloring as $1$-cochain $f^1:\ E(\Gamma)\to{\mathbb Z}_2$, where black corresponds to $0$ and white to $1$. Let $\Gamma'=(V',E')$ be a connected component of $\Gamma$ and select a spanning tree $T$ of $\Gamma'$. Since $T$ is simply connected there exists a $0$-cochain $f^0:\ V'\to{\mathbb Z}_2$ such that for all edges $e=\{u,v\}$ of $T$ one has $$f^1(e)=f^0(u)-f^0(v)\ .\tag{1}$$ Two vertices $v_1$, $v_2$ of $\Gamma'$ get the same $f^0$-value iff walking from $v_1$ to $v_2$ along edges of $T$ one passes through an even number of white edges. This $f^0:\ V'\to{\mathbb Z}_2$ is determined up to an additive constant; so there are exactly two such $f^0$. When $e=\{u,v\}$ is an edge of $\Gamma'$ which is not in $T$ then the coboundary condition $(1)$ is automatically fulfilled for $e$; because otherwise one could at once exhibit a bad cycle in $\Gamma$.

When the above construction has been performed on each of the $b_0$ components of $\Gamma$ one can collect the chosen partial $f^0$ to a global $f^0:\ V(K_n)\to{\mathbb Z}_2$ and then finally color the remaining uncolored edges of $K_n$ such that the condition $(1)$ is fulfilled throughout. It is easy to see that the resulting edge-coloring of $K_n$ is admissible.

Given the $b_0$ choices we had when fixing the partial $f^0:\ V'\to{\mathbb Z}_2$ it follows that (ii) can be considered proven as well.


Hint: Given a (complete) coloring of the clique, each vertex of the form $v_{i} v_{i+2}$ is uniquely determined.

It then remains to check that triangles of the form $v_i , v_{i+2}, v_{i+4} $ satisfy the conditions.

Hint: Assume that such a coloring is possible. Label the black edges $-1$ and the white edges $1$. Then, we know that the product each triangle is $-1$. Use this to get conditions on the edges.

  • $\begingroup$ what do you mean when you say "each vertex of the form vivi+2 is uniquely determined" $\endgroup$ Sep 26 '13 at 15:28
  • $\begingroup$ Can you please explain your method ( the first hint ). $\endgroup$ Sep 26 '13 at 19:11
  • $\begingroup$ @user2179293 If $v_i v_{i+1}$ is black and $v_{i+1} v_{i+2}$ is white, what must be the color of $v_i v_{i+2}$? Do this for the different combinations of black and white. $\endgroup$
    – Calvin Lin
    Sep 26 '13 at 20:20

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.