Flip colouring of graphs II

Abstract

We give results concerning two problems on the recently introduced \textit{flip colourings of graphs}. For positive integers $b,r$ with $b<r$, we say that a $b+r$ regular graph is a $(b,r)$-\textit{flip graph} if there exists a red/blue edge colouring such that the red degree of every vertex is $r$, the blue degree of every vertex is $b$, yet in the closed neighbourhood of every vertex there are more blue edges than red edges. We prove that for integers $b,r$ with $4\le b<r<b+2{\lfloor \frac{b+2}{6}\rfloor }^2$, small constructions of $(b,r)$-flip graphs on $\hat{I}˜(b+r)$ vertices are possible. Furthermore, we prove that there exist $k$-flip sequences $(a_1,\dots ,a_k)$ where $k>4$, such that $a_k$ can be arbitrarily large whilst $a_i$ is constant for $1\le i<\frac{k}{4}$.

15 pages, 6 figures. Final journal version; to appear in BICA