0
$\begingroup$

My apologies for asking so many questions recently.

Let $0\le c<d<e$ be fixed natural numbers and consider any graph on $2e$ vertices, with the vertices labelled as $0,1,\cdots 2e-1$. I want to color the vertices red and blue so that the following property holds:

For any vertex $u$, if $u$ is colored red then for any $x,y,z$ such that $\{x,y,z\}=\{c,d,e\}$ at least one amongst $u+x-y$ or $u+z-y$ (assuming it makes sense as a vertex) is colored blue. Likewise if $u$ is colored blue then for any $x,y,z$ such that $\{x,y,z\}=\{c,d,e\}$ at least one amongst $u+x-y$ or $u+z-y$ is colored red. Basically I want that the set $\{u,u+x-y,u+z-y\}$ should not be monochromatic.

How can I get such a vertex coloring? Is it impossible to get such a coloring? (I don't know.)

I'll be grateful for any suggestions or comments.

$\endgroup$
0

1 Answer 1

0
$\begingroup$

I asked the question on mathoverflow and got the answer: The given problem is equivalent to $2$-coloring a hypergraph on $2e$ vertices where each hyperedge is given by $\{c+v,d+v,e+v\}$, where $0\le v\le e-1$. Considering the bipartite graph obtained by removing $d+v$ from each hyperedge we immediately see that the hypergraph is $2$-colorable.

$\endgroup$

You must log in to answer this question.