On a problem concerning integer distance graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914649001164800 |
|---|---|
| author | Oravcová, Janka Soták, Roman |
| author_facet | Oravcová, Janka Soták, Roman |
| contents | 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 $χ(G(D)) \leq |D|+1$.
This article studies the problem (which is motivated by a conjecture of Zhu): "Is it true that $χ(G(D)) = |D|+1$ implies $ω(G(D)) \geq |D|+1$, where $ω(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 $χ(G(D))=|D|+1$ but $ω(G(D))=|D|-1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_12347 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On a problem concerning integer distance graphs Oravcová, Janka Soták, Roman Combinatorics 05C15, 05C63, 05C75 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 $χ(G(D)) \leq |D|+1$. This article studies the problem (which is motivated by a conjecture of Zhu): "Is it true that $χ(G(D)) = |D|+1$ implies $ω(G(D)) \geq |D|+1$, where $ω(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 $χ(G(D))=|D|+1$ but $ω(G(D))=|D|-1$. |
| title | On a problem concerning integer distance graphs |
| topic | Combinatorics 05C15, 05C63, 05C75 |
| url | https://arxiv.org/abs/2401.12347 |