Making a K₄-free graph bipartite
From MaRDI portal
Publication:950329
DOI10.1007/S00493-007-2238-0zbMATH Open1164.05035arXiv0706.4101OpenAlexW2087280368MaRDI QIDQ950329FDOQ950329
Publication date: 22 October 2008
Published in: Combinatorica (Search for Journal in Brave)
Abstract: We show that every K_4-free graph G with n vertices can be made bipartite by deleting at most n^2/9 edges. Moreover, the only extremal graph which requires deletion of that many edges is a complete 3-partite graph with parts of size n/3. This proves an old conjecture of P. Erdos.
Full work available at URL: https://arxiv.org/abs/0706.4101
Recommendations
- Making a \(C_6\)-free graph \(C_4\)-free and bipartite
- Making Kr+1-free graphs r-partite
- Arbitrarily partitionable \(\{2K_2, C_4\}\)-free graphs
- \(K_{4}\)-free graphs with no odd holes
- scientific article
- Making an H $H$‐free graph k $k$‐colorable
- Extremal <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msub><mml:mi>K</mml:mi><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>s</mml:mi><mml:mo>,</mml:mo><mml:mi>t</mml:mi><mml:mo stretchy="false">)<
- Extremal \(K_{(s,t)}\)-free bipartite graphs
- K4$K_4$‐free graphs have sparse halves
- Vertex partitions of \(K_{4,4}\)-minor free graphs
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- How to make a graph bipartite
- Maximum cuts and judicious partitions in graphs without short cycles
- Bipartite subgraphs
- Title not available (Why is that?)
- Some Extremal Properties of Bipartite Subgraphs
- MaxCut in ${\bm H)$-Free Graphs
- On the edge distribution in triangle-free graphs
- Local Density in Graphs with Forbidden Subgraphs
- Sparse halves in triangle-free graphs
- Title not available (Why is that?)
- Largest bipartite subgraphs in triangle-free graphs with maximum degree three
- A note on bipartite subgraphs of triangle‐free graphs
Cited In (13)
- Title not available (Why is that?)
- The clique number and the smallest \(Q\)-eigenvalue of graphs
- A note on bipartite subgraphs and triangle-independent sets
- On the edge distribution of a graph
- Dense induced bipartite subgraphs in triangle-free graphs
- Sparse halves in triangle-free graphs
- Lower Bounds for Max-Cut in $H$-Free Graphs via Semidefinite Programming
- Exact stability for Turán’s Theorem
- 10 problems for partitions of triangle-free graphs
- Sparse halves in K4‐free graphs
- Making Kr+1-free graphs r-partite
- Making an H $H$‐free graph k $k$‐colorable
- K4$K_4$‐free graphs have sparse halves
This page was built for publication: Making a \(K_4\)-free graph bipartite
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q950329)
