Trees, ladders and graphs

2014/09/09 by Dániel T. Soukup, Soukup, Dániel T.
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #Limits and Structures in Graph Theory #math.CO #math.LO #msc:03E05 #msc:05C15 #msc:05C63

paper · pdf · doi:10.48550/arxiv.1409.2922

23 pages, 2 figures, submitted to the Journal of Comb. Theory Series B

arxiv created 2014/09/09 · arxiv updated 2014/09/11

Abstract

We introduce a new method to construct uncountably chromatic graphs from non special trees and ladder systems. Answering a question of P. Erdős and A. Hajnal from 1985, we construct graphs of chromatic number ω₁ without uncountable ω-connected subgraphs. Second, we build triangle free graphs of chromatic number ω₁ without subgraphs isomorphic to H_ω,ω+2.

Related

• A note on uncountably chromatic graphs
• Separating Tree-chromatic number from Path-chromatic Number
• Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path
• Structure and colour in triangle-free graphs
• Tree‐Chromatic Number Is Not Equal to Path‐Chromatic Number*