Flip colouring of graphs

Abstract

It is proved that for integers b,r such that 3≤b<r≤(b+12)−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≤(b+12)−1 is best possible for any b≥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≤t≤r22−5r3/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.