Infinitely connected subgraphs in graphs of uncountable chromatic number

Research output: Contribution to journalJournal articleResearchpeer-review

267 Downloads (Pure)

Abstract

Erdős and Hajnal conjectured in 1966 that every graph of uncountable chromatic number contains a subgraph of infinite connectivity. We prove that every graph of uncountable chromatic number has a subgraph which has uncountable chromatic number and infinite edge-connectivity. We also prove that, if each orientation of a graph G has a vertex of infinite outdegree, then G contains an uncountable subgraph of infinite edge-connectivity.
Original languageEnglish
JournalCombinatorica
Volume37
Issue number4
Pages (from-to)785–793
ISSN0209-9683
DOIs
Publication statusPublished - 2016

Fingerprint Dive into the research topics of 'Infinitely connected subgraphs in graphs of uncountable chromatic number'. Together they form a unique fingerprint.

Cite this