Bipartification conjecture for homomorphic preimages of Andrásfai graphs

Let Andk\textnormal{And}_k be the Andrásfai graph, and let HH be an arbitrary homomorphic preimage of Andk\textnormal{And}_k. Let FkF_k be the bipartification defined in Theorem. Homomorphic-preimage bipartification conjecture. By considering several copies of the bipartification FkF_k, and then optimizing a system of quadratic inequalities, it is possible to prove that HH can be made bipartite by deleting at most

125H2\frac{1}{25}|H|^2

edges. This is described as a special case relevant to the Erdős bipartification conjecture; the source does not provide a proof or resolution.

Sources & referencesView supporting material

Primary source

Peter Christian Heinig, “The Erdős bipartification conjecture is true in the special case of Andrásfai graphs”, arXiv:0907.3928 (2009).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.