Photo from wikipedia
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… Click to show full 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.
Keywords:
connected subgraphs;
uncountable chromatic;
subgraphs graphs;
infinitely connected;
chromatic number
Journal Title: Combinatorica
Year Published: 2017
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!
Journal Title: Combinatorica
Year Published: 2017
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!