Hedetniemi's conjecture for uncountable graphs

DOI10.4171/JEMS/666zbMATH Open1423.03238arXiv1307.6841OpenAlexW2964274373WikidataQ123252471 ScholiaQ123252471MaRDI QIDQ509108FDOQ509108

Authors: Assaf Rinot 

Publication date: 8 February 2017

Published in: Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

Abstract: It is proved that in Godel's constructible universe, for every infinite successor cardinal k, there exist graphs G and H of size and chromatic number k, for which the tensor product graph (G x H) is countably chromatic.

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

Recommendations

• The chromatic number of the product of two \(\aleph _ 1\)-chromatic graphs can be countable
• scientific article; zbMATH DE number 4047709
• Hadwiger's conjecture for uncountable graphs
• scientific article; zbMATH DE number 426350
• scientific article; zbMATH DE number 4208094

zbMATH Keywords

product graphHedetniemi's conjectureconstructible universealmost countably chromaticincompactnessOstaszewski square

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Infinite graphs (05C63) Other combinatorial set theory (03E05) Consistency and independence results (03E35) Applications of set theory (03E75)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Ostaszewski square and homogeneous Souslin trees
• Chromatic numbers of graphs -- large gaps
• Generic graph construction
• On chromatic number of graphs and set-systems
• Title not available (Why is that?)
• Whitehead groups may be not free, even assuming CH. I
• On the arc-chromatic number of a digraph
• Title not available (Why is that?)
• The chromatic number of the product of two \(\aleph _ 1\)-chromatic graphs can be countable
• Whitehead groups may not be free even assuming CH. II
• A \({\Delta{}}^ 2_ 2\) well-order of the reals and incompactness of \(L(Q^{MM})\)
• Same graph, different universe
• Some results on higher Suslin trees
• Title not available (Why is that?)
• Infinite combinatorics: from finite to infinite
• Squares with diamonds and Souslin trees with special squares
• A Note on the Combinatorial Principles ◊(E)
• A new construction of non-constructible ${Δ^1}_3$ subset of ω
• Putting a diamond inside the square

Cited In (10)

• The countable character of uncountable graphs
• Counterexamples to Hedetniemi's conjecture
• Square with built-in diamond-plus
• A note on conjectures of F. Galvin and R. Rado
• Generic automorphisms and graph coloring
• Title not available (Why is that?)
• Hadwiger's conjecture for uncountable graphs
• Putting a diamond inside the square
• The chromatic number of the product of two \(\aleph _ 1\)-chromatic graphs can be countable
• The uncountable Hadwiger conjecture and characterizations of trees using graphs

This page was built for publication: Hedetniemi's conjecture for uncountable graphs

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