The Erdős bipartification conjecture is true in the special case of Andrásfai graphs

Abstract

Let the Andrásfai graph ${\mathrm{And}}_k$ be defined as the graph with vertex set $\{v_0,v_1,...c,v_{3k-2}\}$ and two vertices $v_i$ and $v_j$ being adjacent iff $|i-j|\equiv 1\mathrm{mod}3$. The graphs ${\mathrm{And}}_k$ are maximal triangle-free and play a role in characterizing triangle-free graphs with large minimum degree as homomorphic preimages. A minimal bipartification of a graph $G$ is defined as a set of edges $F\subset E(G)$ having the property that the graph $(V(G),E(G)\backslash F)$ is bipartite and for every $e\in F$ the graph $(V(G),E(G)\backslash (F\backslash e))$ is not bipartite. In this note it is shown that there is a minimal bipartification $F_k$ of ${\mathrm{And}}_k$ which consists of exactly $\lfloor \frac{k^2}{4}\rfloor$ edges. This equals $\lfloor 1/36(|{\mathrm{And}}_k|+1{)}^2\rfloor$, where $|\cdot |$ denotes the number of vertices of a graph. For all $k$ this is consistent with a conjecture of Paul Erdős that every triangle-free graph $G$ can be made bipartite by deleting at most $1/25|G{|}^2$ edges. Bipartifications like $F_k$ may be useful for proving that arbitrary homomorphic preimages of an Andrásfai graph can be made bipartite by deleting at most $1/25|G{|}^2$ edges.

7 pages, 0 figures; several small corrections, simplified main formula