Non-Three-Colourable Common Graphs Exist

DOI10.1017/S0963548312000107zbMath1248.05090DBLPjournals/cpc/HatamiHKNR12arXiv1105.0307WikidataQ57601388 ScholiaQ57601388MaRDI QIDQ2911071

Hamed Hatami, Jan Hladký, Daniel Král', Serguei Norine, Alexander A. Razborov

Publication date: 12 September 2012

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

5-wheelcommon graphsnumber of copies

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Related Items (29)

On tripartite common graphs ⋮ Finitely forcible graph limits are universal ⋮ The step Sidorenko property and non-norming edge-transitive graphs ⋮ Threshold Ramsey multiplicity for odd cycles ⋮ Non-bipartite \(k\)-common graphs ⋮ Locally common graphs ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ Toward characterizing locally common graphs ⋮ A Property on Monochromatic Copies of Graphs Containing a Triangle ⋮ Common graphs with arbitrary connectivity and chromatic number ⋮ Extended commonality of paths and cycles via Schur convexity ⋮ Minimum Number of Monotone Subsequences of Length 4 in Permutations ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs ⋮ Finitely forcible graphons with an almost arbitrary structure ⋮ A new lower bound based on Gromov's method of selecting heavily covered points ⋮ Monochromatic triangles in three-coloured graphs ⋮ Finitely forcible graphons and permutons ⋮ Extremal problems and results related to Gallai-colorings ⋮ Counting flags in triangle-free digraphs ⋮ A New Bound for the 2/3 Conjecture ⋮ Decomposing Graphs into Edges and Triangles ⋮ More about sparse halves in triangle-free graphs ⋮ Minimum number of edges that occur in odd cycles ⋮ Weak regularity and finitely forcible graph limits ⋮ Threshold Ramsey multiplicity for paths and even cycles ⋮ Compactness and finite forcibility of graphons ⋮ On the algebraic and topological structure of the set of Turán densities ⋮ On the Density of Transitive Tournaments

Cites Work

• Unnamed Item
• An approximate version of Sidorenko's conjecture
• Graphs containing triangles are not 3-common
• Multiplicities of subgraphs
• A correlation inequality for bipartite graphs
• On 3-Hypergraphs with Forbidden 4-Vertex Configurations
• Hypergraphs Do Jump
• On Sets of Acquaintances and Strangers at any Party
• A Disproof of a Conjecture of Erdős in Ramsey Theory
• On the Ramsey multiplicities of graphs—problems and recent results
• Flag algebras
• Quasi-random graphs
• Graph norms and Sidorenko's conjecture

This page was built for publication: Non-Three-Colourable Common Graphs Exist