K4K₄‐free graphs have sparse halves

DOI10.1112/BLMS.12782MaRDI QIDQ6096775zbMATH OpenOpenAlexFDO

Authors Christian Reiher

Publication date 15 September 2023

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2108.07297

zbMATH Keywords

Mantel's theorembalanced tripartite graphssparse halves conjecture

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42)

Abstract: Every $K_4$-free graph on $n$ vertices has a set of $lfloorn/2floor$ vertices spanning at most $n^2/18$ edges.

Recommendations

• Sparse halves in K4‐free graphs
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• Sparse halves in triangle-free graphs
• Making a K₄-free graph bipartite
• \(K_4\)-minor-free induced subgraphs of sparse connected graphs

Cites work

• scientific article; zbMATH DE number 15664 (Why is no real title available?)
• scientific article; zbMATH DE number 3523543 (Why is no real title available?)
• scientific article; zbMATH DE number 3435529 (Why is no real title available?)
• A local density condition for triangles
• More about sparse halves in triangle-free graphs
• More results on Ramsey-Turán type problems
• On a Ramsey-Turán type problem
• On the Ramsey-Turán density of triangles
• On the edge distribution in triangle-free graphs
• Some old and new problems in various branches of combinatorics
• Sparse halves in K4‐free graphs
• Sparse halves in dense triangle-free graphs
• Sparse halves in triangle-free graphs
• The Ramsey-Turán problem for cliques
• The critical window for the classical Ramsey-Turán problem
• Triangle-free graphs whose independence number equals the degree
• Über ein Extremalproblem der Graphentheorie

Cited in

(5)

• Making a K₄-free graph bipartite
• 10 problems for partitions of triangle-free graphs
• Graphs in which each \(C_4\) spans \(K_4\)
• \(K_4\)-minor-free induced subgraphs of sparse connected graphs
• Sparse halves in K4‐free graphs

This page was built for publication: K4$K_4$‐free graphs have sparse halves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6096775)