On the independence ratio of distance graphs
From MaRDI portal
Publication:738864
DOI10.1016/J.DISC.2016.05.018zbMATH Open1343.05055arXiv1401.7183OpenAlexW1572592322MaRDI QIDQ738864FDOQ738864
Authors: James M. Carraher, David Galvin, Stephen G. Hartke, Derrick Stolee, Andrew John Radcliffe 
Publication date: 16 August 2016
Published in: Discrete Mathematics (Search for Journal in Brave)
Abstract: A distance graph is an undirected graph on the integers where two integers are adjacent if their difference is in a prescribed distance set. The independence ratio of a distance graph is the maximum density of an independent set in . Lih, Liu, and Zhu [Star extremal circulant graphs, SIAM J. Discrete Math. 12 (1999) 491--499] showed that the independence ratio is equal to the inverse of the fractional chromatic number, thus relating the concept to the well studied question of finding the chromatic number of distance graphs. We prove that the independence ratio of a distance graph is achieved by a periodic set, and we present a framework for discharging arguments to demonstrate upper bounds on the independence ratio. With these tools, we determine the exact independence ratio for several infinite families of distance sets of size three, determine asymptotic values for others, and present several conjectures.
Full work available at URL: https://arxiv.org/abs/1401.7183
Recommendations
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Uniquely \(K_r\)-saturated graphs
- Circulants and Sequences
- On planarity and colorability of circulant graphs
- The packing coloring of distance graphs \(D(k,t)\)
- Packing chromatic number of distance graphs
- Some properties of unitary Cayley graphs
- Distance graphs and \(T\)-coloring
- The chromatic numbers of distance graphs
- Counting sets with small sumset, and the clique number of random Cayley graphs
- Colouring the real line
- Integral distance graphs
- Colouring prime distance graphs
- Hardness results and spectral techniques for combinatorial problems on circulant graphs
- Bounds for Ramsey numbers of complete graphs dropping an edge
- Distance graphs with finite chromatic number
- On packing colorings of distance graphs
- Distance graphs with maximum chromatic number
- Some colouring problems for Paley graphs
- From rainbow to the lonely runner: A survey on coloring parameters of distances graphs
- On the clique number of integral circulant graphs
- On the chromatic number of integral circulant graphs
- The energy of unitary Cayley graphs
- Title not available (Why is that?)
- CLIQUE NUMBERS OF PALEY GRAPHS
- Circular chromatic number of distance graphs with distance sets of cardinality 3
- Star Extremal Circulant Graphs
- Circular chromatic numbers and fractional chromatic numbers of distance graphs
- Coloring of integer distance graphs
- Coloring of distance graphs with intervals as distance sets
- Fractional chromatic number and circular chromatic number for distance graphs with large clique size
- Star-extremal graphs and the lexicographic product
- Maximal cliques in the Paley graph of square order
- Distance-regular circulants
- Chromatic number of distance graphs generated by the sets \(\{2,3,x,y\}\)
- Proof of a conjecture on fractional Ramsey numbers
- THE CLIQUE NUMBERS AND CHROMATIC NUMBERS OF CERTAIN PALEY GRAPHS
- Title not available (Why is that?)
- Title not available (Why is that?)
- Chromatic numbers of Cayley graphs on \(\mathbb Z\) and recurrence
Cited In (9)
- On optimal \(M\)-sets related to Motzkin's problem
- On the independence number of minimum distance graphs
- Independence numbers of random subgraphs of a distance graph
- Bipartite density and the independence ratio
- On the independence numbers of some distance graphs with vertices in \(\{-1, 0, 1\}^n\)
- Sequences of integers with three missing separations
- Domination ratio of a family of integer distance digraphs with arbitrary degree
- Maximal density of integral sets with missing differences and the kappa values
- Domination ratio of integer distance digraphs
Uses Software
This page was built for publication: On the independence ratio of distance graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q738864)
