Back to Search
Start Over
On a problem concerning integer distance graphs
- Publication Year :
- 2024
-
Abstract
- For $D$ being a subset of positive integers, the integer distance graph is the graph $G(D)$, whose vertex set is the set of integers, and edge set is the set of all pairs $uv$ with $|u-v| \in D$. It is known that $\chi(G(D)) \leq |D|+1$. This article studies the problem (which is motivated by a conjecture of Zhu): "Is it true that $\chi(G(D)) = |D|+1$ implies $\omega(G(D)) \geq |D|+1$, where $\omega(H)$ is the clique number of $H$?". We give a negative answer to this question, by showing an infinite class of integer distance graphs with $\chi(G(D))=|D|+1$ but $\omega(G(D))=|D|-1$.
- Subjects :
- Mathematics - Combinatorics
05C15, 05C63, 05C75
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2401.12347
- Document Type :
- Working Paper