Bipartification conjecture for homomorphic preimages of Andrásfai graphs
Bipartification conjecture for homomorphic preimages of Andrásfai graphs
Let be the Andrásfai graph, and let be an arbitrary homomorphic preimage of . Let be the bipartification defined in Theorem. Homomorphic-preimage bipartification conjecture. By considering several copies of the bipartification , and then optimizing a system of quadratic inequalities, it is possible to prove that can be made bipartite by deleting at most
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.