Home » Subject » Graph Theory

Chromatic Number of Common Graphs

Importance: Medium ✭✭
Author(s): Hatami, H
Hladký, J.
Kráľ, D.
Norine, S.
Razborov, A.
Subject: Graph Theory
Keywords: common graph
Recomm. for undergrads: no
Posted by: David Wood
on: August 15th, 2014
Question   Do common graphs have bounded chromatic number?

A graph $ H $ is common if the sum of the number of copies of $ H $ in a graph $ G $ and the number in the complement of $ G $ is asymptotically minimised by taking $ G $ to be a random graph (see [HHKNR] for a formal definition).

Goodman proved that $ K_3 $ is common [G]. Erdös [E] conjectured that every complete graph is common. Later, this conjecture was extended to all graphs by Burr and Rosta [BR]. Sidorenko [S89] disproved Burr and Rosta’s conjecture by showing that a triangle with a pendant edge is not common. Conjectures of Erdös and Simonovits [ES] and Sidorenko [S91,S93] imply that every bipartite graph is common. Disproving the first conjecture of Erdös, Thomason proved that $ K_4 $ is not common [T]. More generally, Jagger, Šťovíček and Thomason proved that no common graph contains $ K_4 $ as a subgraph [JST]. The 5-wheel is an example of a 4-chromatic common graph [HHKNR].

Related problems

Sidorenko's Conjecture

Bibliography

[BR] Burr, S. A. and Rosta, V. On the Ramsey multiplicities of graphs: Problems and recent results. J. Graph Theory 4 (1980) 347–361.

[E] Paul Erdös, On the number of complete subgraphs contained in certain graphs. Magyar Tud. Akad. Mat. Kutato ́ Int. Ko ̈zl. 7 (1962) 459–464.

[ES] Paul Erdös and Miklós Simonovits (1984) Cube-supersaturated graphs and related problems. In Progress in Graph Theory: Waterloo, Ont., 1982, Academic Press, pp. 203–218.

*[HHKNR] H. Hatami, J. Hladký, D. Kráľ, S. Norine, A. Razborov: Non-three-colorable common graphs exist, Combinatorics, Probability and Computing 21 (2012), 734–742.

[JST] Jagger, Chris; Šťovíček, Pavel; Thomason, Andrew. Multiplicities of subgraphs. Combinatorica 16 (1996) 123–141.

[S89] Sidorenko, A. Cycles in graphs and functional inequalities. Mat. Zametki 46 (1989) 72–79, 104.

[S91] Sidorenko, A. Inequalities for functionals generated by bipartite graphs. Diskret. Mat. 3 (1991) 50–65.

[S93] Sidorenko, A. A correlation inequality for bipartite graphs. Graphs Combin. 9 (1993) 201–204.

[T] Thomason, Andrew. A disproof of a conjecture of Erdo ̋s in Ramsey theory, J. London Math. Soc. (2) 39 (1989) 246–255.


* indicates original appearance(s) of problem.
add new comment