Mathematics – Combinatorics
Scientific paper
2009-07-23
Mathematics
Combinatorics
7 pages, 0 figures; several small corrections, simplified main formula
Scientific paper
Let the Andr\'{a}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\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}\bigl(|\mathrm{And}_k|+1\bigr)^2\rfloor$, where $|\cdot|$ denotes the number of vertices of a graph. For all $k$ this is consistent with a conjecture of Paul Erd\H{o}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\'{a}sfai graph can be made bipartite by deleting at most ${1/25} |G|^2$ edges.
No associations
LandOfFree
The Erdős bipartification conjecture is true in the special case of Andrásfai graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Erdős bipartification conjecture is true in the special case of Andrásfai graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Erdős bipartification conjecture is true in the special case of Andrásfai graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-354170