New upper bound for the chromatic number of a random subgraph of a distance graph

DOI10.1134/S0001434615030037zbMath1316.05043MaRDI QIDQ2352580

A. S. Gusev

Publication date: 3 July 2015

Published in: Mathematical Notes (Search for Journal in Brave)

zbMATH Keywords

chromatic numberdistance graphTurán numberHadwiger-Nelson problemrandom subgraph

Mathematics Subject Classification ID

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

Related Items (5)

On the chromatic numbers of low-dimensional spaces ⋮ On the chromatic number of a random subgraph of the Kneser graph ⋮ On threshold probability for the stability of independent sets in distance graphs ⋮ Clique numbers of random subgraphs of some distance graphs ⋮ On the chromatic number of random subgraphs of a certain distance graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On random subgraphs of Kneser and Schrijver graphs
• An improvement of the Frankl-Wilson theorem on the number of edges in a hypergraph with forbidden intersections of edges
• On the chromatic numbers of spheres in \(\mathbb R^n\)
• Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs
• Borsuk's problem for \((0,1)\)-polytopes and cross-polytopes
• The problem of Borsuk, Hadwiger,and Grünbaum for some classes of polytopes and graphs
• On the stability of the Erdős-Ko-Rado theorem
• On a packing and covering problem
• The Borsuk problem for \((0,1)\)-polyhedra and cross polytopes.
• What we know and what we do not know about Turán numbers
• Codes with forbidden distances
• New estimates in the problem of the number of edges in a hypergraph with forbidden intersections
• Borsuk's problem and the chromatic numbers of some metric spaces
• Coloring Distance Graphs and Graphs of Diameters
• Coloring some finite sets in {R}^{n}
• Research Problems in Discrete Geometry
• The problems of Borsuk and Grunbaum on lattice polytopes
• The Mathematical Coloring Book
• On the Ramsey numbers for complete distance graphs with vertices in $ \{0,1\}^n$
• The Erdõs-Hadwiger problem and the chromatic numbers of finite geometric graphs
• The chromatic number of random graphs
• The chromatic number of random graphs

This page was built for publication: New upper bound for the chromatic number of a random subgraph of a distance graph