English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let the Andr\'{a}sfai graph $\mathrm{And}_k$ be defined as the graph withvertex set $\{v_0,v_1,...c, v_{3k-2}\}$ and two vertices $v_i$ and $v_j$ beingadjacent iff $|i-j| \equiv 1\mod 3$. The graphs $\mathrm{And}_k$ are maximaltriangle-free and play a role in characterizing triangle-free graphs with largeminimum 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 thegraph $(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 isshown that there is a minimal bipartification $F_k$ of $\mathrm{And}_k$ whichconsists of exactly $\lfloor\frac{k^2}{4}\rfloor$ edges. This equals$\lfloor{1/36}\bigl(|\mathrm{And}_k|+1\bigr)^2\rfloor$, where $|\cdot|$ denotesthe number of vertices of a graph. For all $k$ this is consistent with aconjecture of Paul Erd\H{o}s that every triangle-free graph $G$ can be madebipartite by deleting at most ${1/25} |G|^2$ edges. Bipartifications like $F_k$may be useful for proving that arbitrary homomorphic preimages of anAndr\'{a}sfai graph can be made bipartite by deleting at most ${1/25} |G|^2$edges.

The Erd\H{o}s bipartification conjecture is true in the special case of Andr\'asfai graphs