K4K₄‐free graphs have sparse halves

DOI10.1112/BLMS.12782zbMATH Open1521.05085arXiv2108.07297OpenAlexW4313365414MaRDI QIDQ6096775FDOQ6096775

Authors: Christian Reiher 

Publication date: 15 September 2023

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

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

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

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_4\)-free graph bipartite
• \(K_4\)-minor-free induced subgraphs of sparse connected graphs

zbMATH Keywords

Mantel's theorembalanced tripartite graphssparse halves conjecture

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Making a \(K_4\)-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)