Erdös--Hajnal Properties for Powers of Sparse Graphs

Autor:	Michał T. Seweryn, Michał Pilipczuk, Marcin Briański, Piotr Micek
Rok vydání:	2021
Předmět:	Combinatorics Discrete mathematics Class (set theory) 010201 computation theory & mathematics Graph power General Mathematics Nowhere dense set 0102 computer and information sciences 16. Peace & justice 01 natural sciences Graph Integer (computer science) Mathematics
Zdroj:	SIAM Journal on Discrete Mathematics. 35:447-464
ISSN:	1095-7146 0895-4801
DOI:	10.1137/20m1342756
Popis:	We prove that for every nowhere dense class of graphs $\mathcal{C}$, positive integer $d$, and $\varepsilon>0$, the following holds: in every $n$-vertex graph $G$ from $\mathcal{C}$ one can find tw...
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::228e9b9e141f8e45a5c6b5934dece01f https://doi.org/10.1137/20m1342756 Zobrazit plný text záznamu