Trees, ladders and graphs

DOI10.1016/J.JCTB.2015.05.004MaRDI QIDQ490986zbMATH OpenOpenAlexFDO

Authors Dániel T. Soukup

Publication date 21 August 2015

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.2922

zbMATH Keywords

ladder systemconnected subgraphnon-special treeuncountably chromatic

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Abstract: We introduce a new method to construct uncountably chromatic graphs from non special trees and ladder systems. Answering a question of P. ErdH{o}s and A. Hajnal from 1985, we construct graphs of chromatic number $omeg{a}_1$ without uncountable $omega$-connected subgraphs. Second, we build triangle free graphs of chromatic number $omeg{a}_1$ without subgraphs isomorphic to $H_{omega,omega+2}$.

Recommendations

• Tree-structured graphs
• Tree representations of graphs
• Trees in Polyhedral Graphs
• scientific article; zbMATH DE number 1693469
• Treetopes and their Graphs
• Treetopes and their graphs
• scientific article; zbMATH DE number 3865291
• Ladder systems on trees
• scientific article; zbMATH DE number 719398
• Tree loop graphs

Cites work

• scientific article; zbMATH DE number 3821802 (Why is no real title available?)
• scientific article; zbMATH DE number 3506705 (Why is no real title available?)
• A Contribution to the Theory of Chromatic Polynomials
• A note on chromatic number and connectivity of infinite graphs
• Chromatic number of finite and infinite graphs and hypergraphs
• Connectivity and chromatic number of infinite graphs
• Consistency results on infinite graphs
• Erdős work on infinite graphs
• Forcing constructions for uncountably chromatic graphs
• Graph Theory and Probability
• Ladder systems on trees
• On chromatic number of graphs and set-systems
• Partition Relations Connected with the Chromatic Number of Graphs
• Set theory.
• The chromatic number of infinite graphs - A survey
• What must and what need not be contained in a graph of uncountable chromatic number?

Cited in

(11)

• The uncountable Hadwiger conjecture and characterizations of trees using graphs
• A note on uncountably chromatic graphs
• Hajnal-Máté graphs, Cohen reals, and disjoint-type guessing
• Ladder systems on trees
• On the connectivity of infinite graphs
• Infinite combinatorics plain and simple
• A counterexample related to a theorem of Komjáth and Weiss
• An uncountably chromatic triple system
• Applications of Order Trees in Infinite Graphs
• Ramsey theory for highly connected monochromatic subgraphs
• Infinitely connected subgraphs in graphs of uncountable chromatic number

This page was built for publication: Trees, ladders and graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490986)