Flip colouring of graphs

Abstract

It is proved that for integers $b,r$ such that $3\le b<r\le \left(\genfrac{}{}{0ex}{}{b+1}{2}\right)-1$, there exists a red/blue edge-colored graph such that the red degree of every vertex is $r$, the blue degree of every vertex is $b$, yet in the closed neighborhood of every vertex there are more blue edges than red edges. The upper bound $r\le \left(\genfrac{}{}{0ex}{}{b+1}{2}\right)-1$ is best possible for any $b\ge 3$. We further extend this theorem to more than two colours, and to larger neighbourhoods. A useful result required in some of our proofs, of independent interest, is that for integers $r,t$ such that $0\le t\le \frac{r^2}{2}-5r^{3/2}$, there exists an $r$-regular graph in which each open neighborhood induces precisely $t$ edges. Several explicit constructions are introduced and relationships with constant linked graphs, $(r,b)$-regular graphs and vertex transitive graphs are revealed.