Trees, ladders and graphs

DOI10.1016/J.JCTB.2015.05.004zbMATH Open1319.05041arXiv1409.2922OpenAlexW2167749725MaRDI QIDQ490986FDOQ490986

Dániel T. Soukup

Publication date: 21 August 2015

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

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}$.

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

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

zbMATH Keywords

ladder systemconnected subgraphnon-special treeuncountably chromatic

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• INFINITE COMBINATORICS PLAIN AND SIMPLE
• Hajnal-Máté graphs, Cohen reals, and disjoint-type guessing
• Ladder systems on trees
• On the connectivity of infinite graphs
• 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)