Non-three-colourable common graphs exist

DOI10.1017/S0963548312000107zbMATH Open1248.05090DBLPjournals/cpc/HatamiHKNR12arXiv1105.0307WikidataQ57601388 ScholiaQ57601388MaRDI QIDQ2911071FDOQ2911071

Authors: Hamed Hatami, Jan Hladký, Daniel Král', Serguei Norine, Alexander Razborov 

Publication date: 12 September 2012

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

Abstract: A graph H is called common if the total number of copies of H in every graph and its complement asymptotically minimizes for random graphs. A former conjecture of Burr and Rosta, extending a conjecture of Erdos asserted that every graph is common. Thomason disproved both conjectures by showing that the complete graph of order four is not common. It is now known that in fact the common graphs are very rare. Answering a question of Sidorenko and of Jagger, Stovicek and Thomason from 1996 we show that the 5-wheel is common. This provides the first example of a common graph that is not three-colorable.

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

Recommendations

• Multiplicities of subgraphs
• Locally common graphs
• Graphs containing triangles are not 3-common
• On tripartite common graphs
• Common graphs with arbitrary connectivity and chromatic number

zbMATH Keywords

5-wheelcommon graphsnumber of copies

Mathematics Subject Classification ID

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

Cites Work

• On 3-hypergraphs with forbidden 4-vertex configurations
• Hypergraphs do jump
• Flag algebras
• Quasi-random graphs
• On Sets of Acquaintances and Strangers at any Party
• A correlation inequality for bipartite graphs
• Graph norms and Sidorenko's conjecture
• Multiplicities of subgraphs
• A Disproof of a Conjecture of Erdős in Ramsey Theory
• On the Ramsey multiplicities of graphs—problems and recent results
• Graphs containing triangles are not 3-common
• An approximate version of Sidorenko's conjecture
• Title not available (Why is that?)

Cited In (32)

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

This page was built for publication: Non-three-colourable common graphs exist

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