Turán type results for distance graphs

DOI10.1007/s00454-016-9817-zzbMath1347.05053OpenAlexW2509064220MaRDI QIDQ331389

Lev E. Shabanov, Andrei M. Raigorodskii

Publication date: 27 October 2016

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-016-9817-z

zbMATH Keywords

independence numberdistance graphsTurán theorem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Distance in graphs (05C12) Erd?s problems and related topics of discrete geometry (52C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Turán-type results for distance graphs in an infinitesimal plane layer, On the minimal number of edges in induced subgraphs of special distance graphs, Turán-type bounds for distance graphs, On complexity of multidistance graph recognition in \(\mathbb{R}^1\), Interview with Andrei Raigorodskii, Estimate of the number of edges in special subgraphs of a distance graph, On the stability of the independence number of a random subgraph, Distance graphs with large chromatic number and without cliques of given size in the rational space, On threshold probability for the stability of independent sets in distance graphs, Chromatic numbers of distance graphs without short odd cycles in rational spaces, A Turán-type theorem for large-distance graphs in Euclidean spaces, and related isodiametric problems, New Turán type bounds for Johnson graphs

Cites Work

• Unnamed Item
• Independence, clique size and maximum degree
• Finding independent sets in \(K_4\)-free 4-regular connected graphs
• 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
• On large subgraphs of a distance graph which have small chromatic number
• Coloring Distance Graphs and Graphs of Diameters
• Research Problems in Discrete Geometry
• Lower bounds on size and independence inK4-free graphs
• Finding Independent Sets in Triangle-Free Graphs
• The realization of distances within sets in Euclidean space
• On Sets of Distances of n Points