On incompactness for chromatic number of graphs

DOI10.1007/S10474-012-0287-3MaRDI QIDQ2448949zbMATH OpenOpenAlexFDO

Authors S. Shelah

Publication date 5 May 2014

Published in Acta Mathematica Hungarica (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numbercompactnessnon-reflecting stationary set

Mathematics Subject Classification ID

Other combinatorial set theory (03E05) Coloring of graphs and hypergraphs (05C15)

Abstract: We deal with incompactness. Assume the existence of non-reflecting stationary set of cofinality kappa . We prove that one can define a graph G whose chromatic number is > kappa, while the chromatic number of every subgraph G' subseteq G,|G'| < |G| is <= kappa . The main case is kappa = aleph_0.

Review text

The main result of the paper reads as follows. Let \(\kappa<\lambda\) be two regular infinite cardinals such that \(\lambda=\lambda^\kappa\) and there exists a non-reflecting stationary set \(S \subseteq\{\alpha<\lambda : \mathrm{cf}(\alpha) = \kappa\}\). Then there is a graph \(G\) with \(\lambda\) nodes and chromatic number \(>\kappa\) such that every subgraph with \(<\lambda\) nodes has chromatic number \(\leq\kappa\).

Recommendations

• scientific article; zbMATH DE number 4200229
• Consistency results on infinite graphs
• Reflection on the coloring and chromatic numbers
• Chromatic numbers of graphs -- large gaps
• On the connectivity of infinite graphs

Cites work

• scientific article; zbMATH DE number 3521967 (Why is no real title available?)
• scientific article; zbMATH DE number 734993 (Why is no real title available?)
• On incompactness for chromatic number of graphs
• Ordered black boxes: existence

Cited in

(12)

• Two remarks on the coloring number
• On the connectivity of infinite graphs
• Additive non-approximability of chromatic number in proper minor-closed classes
• The chromatic number of infinite graphs - A survey
• On incompactness for chromatic number of graphs
• Erdős and set theory
• Chromatic numbers of graphs -- large gaps
• scientific article; zbMATH DE number 4200229 (Why is no real title available?)
• On improperly chromatic-choosable graphs
• Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs
• STATIONARY REFLECTION
• A club guessing toolbox. I

This page was built for publication: On incompactness for chromatic number of graphs

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