2016/02/13 by Sergey Norin, Yue Sun, Norin, Sergey +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1602.04370
arxiv created 2016/02/13 · openalex publication_date 2016/02/13 · arxiv updated 2016/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A set of edges T in a graph G is triangle-independent if T contains at most one edge from each triangle in G. Let α1(G) denote the maximum size of the triangle-independent set in G, and let τB(G) denote minimum size of a set F ⊆ E(G) such that G ∖ F is bipartite. We prove that α1(G) + τB(G) ≤ (|V(G)|2)/(4), verifying a conjecture due to Lehel, and independently Puleo, and a slightly weaker conjecture of Erdős, Gallai and Tuza. Further, we characterize the graphs which attain the equality.