For most graphs H, most H-free graphs have a linear homogeneous set

Autor:	Bruce Reed, Ross J. Kang, Alex Scott, Colin McDiarmid
Rok vydání:	2013
Předmět:	Block graph Discrete mathematics Applied Mathematics General Mathematics Computer Graphics and Computer-Aided Design Erdős–Gyárfás conjecture Degeneracy (graph theory) Combinatorics Triangle-free graph Cograph Split graph Software Mathematics Universal graph Forbidden graph characterization
Zdroj:	Random Structures and Algorithms. 45(3)
ISSN:	1098-2418 1042-9832
Popis:	Erdős and Hajnal conjectured that for every graph H there is a constant such that every graph G that does not have H as an induced subgraph contains a clique or a stable set of order . The conjecture would be false if we set ; however, in an asymptotic setting, we obtain this strengthened form of Erdős and Hajnal's conjecture for almost every graph H, and in particular for a large class of graphs H defined by variants of the colouring number. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 343–361, 2014
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0bc1caadf3ece0009cde5e80e67800ae http://ora.ox.ac.uk/objects/uuid:e576d8aa-7e19-4ff2-b281-d9665b27fca8 Zobrazit plný text záznamu Plný text