J 2012

Non-Three-Colourable Common Graphs Exist

HATAMI, H; J HLADKY; Daniel KRÁĽ; S NORINE; A RAZBOROV et al.

Základní údaje

Originální název

Non-Three-Colourable Common Graphs Exist

Autoři

HATAMI, H; J HLADKY; Daniel KRÁĽ; S NORINE a A RAZBOROV

Vydání

COMBINATORICS PROBABILITY & COMPUTING, NEW YORK, CAMBRIDGE UNIV PRESS, 2012, 0963-5483

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.608

Označené pro přenos do RIV

Ne

DOI

UT WoS

Změněno: 6. 11. 2020 09:04, Mgr. Darina Boukalová

Anotace

V originále

A graph H is called 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 minimized by taking G to be a random graph. Extending a conjecture of Erdos, Burr and Rosta conjectured that every graph is common. Thomason disproved both conjectures by showing that K-4 is not common. It is now known that in fact the common graphs are very rare. Answering a question of Sidorenko and of Jagger, St' ovicek 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-colourable.