On large subgraphs with small chromatic numbers contained in distance graphs

DOI10.1007/S10958-016-2804-3zbMATH Open1337.05042OpenAlexW2301099313MaRDI QIDQ289740FDOQ289740

Authors: A. A. Kokotkin, Andrei M. Raigorodskii 

Publication date: 31 May 2016

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10958-016-2804-3

Recommendations

• On large subgraphs of a distance graph which have small chromatic number
• On the chromatic number of random subgraphs of a certain distance graph
• Distance graphs with large chromatic number and without large cliques
• Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
• Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers

zbMATH Keywords

distance graph on a plane

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Research Problems in Discrete Geometry
• The Erdős-Hadwiger problem and the chromatic numbers of finite geometric graphs
• Random graphs.
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Borsuk's problem and the chromatic numbers of some metric spaces
• The Mathematical Coloring Book
• Title not available (Why is that?)
• On the chromatic number of a space
• The realization of distances within sets in Euclidean space
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A 15-colouring of 3-space omitting distance one
• On the space chromatic number
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (4)

• One problem on geometric Ramsey numbers
• On graphs with small subgraphs of large chromatic number
• Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
• Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii

This page was built for publication: On large subgraphs with small chromatic numbers contained in distance graphs

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