On a generalized Erdős–Rademacher problem

DOI10.1002/JGT.22768MaRDI QIDQ6057585zbMATH OpenOpenAlexFDO

Authors Xizhi Liu, Dhruv Mubayi

Publication date 5 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

color critical graphsErdős-Rademacher problemtriangle covering number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The triangle covering number of a graph is the minimum number of vertices that hit all triangles. Given positive integers $s,t$ and an $n$-vertex graph $G$ with $lfloor{n}^2/4floor+t$ edges and triangle covering number $s$, we determine (for large $n$) sharp bounds on the minimum number of triangles in $G$ and also describe the extremal constructions. Similar results are proved for cliques of larger size and color critical graphs. This extends classical work of Rademacher, ErdH os, and Lov'asz-Simonovits whose results apply only to $slet$. Our results also address two conjectures of Xiao and Katona. We prove one of them and give a counterexample and prove a modified version of the other conjecture.

Recommendations

• scientific article; zbMATH DE number 24365
• On a generalization of a problem of Erdős and Graham
• scientific article; zbMATH DE number 828353
• On stability of the Erdős-Rademacher problem
• A generalization of the Erdős-Surányi problem
• On a generalization of the Erdös-Fuchs theorem
• On a problem of Erdős and Rado
• A generalization of the Erdős-Ko-Rado theorem
• A generalization of the Erdős-Ko-Rado theorem
• A Generalization of the Erdös-Kac Theorem and its Applications

Cites work

• Counting substructures. I: Color critical graphs
• scientific article; zbMATH DE number 3821782 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• On a theorem of Rademacher-Turán
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The number of triangles is more when they have no common vertex

Cited in

(15)

• The minimum number of triangles in graphs of given order and size
• Erdős-Littlewood-Offord problem with arbitrary probabilities
• On a problem of Radko Mesiar: general form of IF-probabilities
• Covering number product bounds size
• The minimum number of triangles covering the edges of a graph
• Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
• The exact minimum number of triangles in graphs with given order and size
• Trinque problem: covering complete graphs by plane degree-bounded hypergraphs
• A Turán-type generalization of Tuza's triangle edge cover problem
• On stability of the Erdős-Rademacher problem
• A spectral Erdős-Rademacher theorem
• Covering the edges of a graph with triangles
• A note on extremal constructions for the Erdős-Rademacher problem
• A spectral Erdős-Faudree-Rousseau theorem
• Spectral supersaturation: triangles and bowties

This page was built for publication: On a generalized Erdős–Rademacher problem

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