Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Distance graphs with ...
Conference paper

Distance graphs with maximum chromatic number

Javier Barajas (1) (2) (3), Oriol Serra ORCID (1) (2) (3)
(1) Universitat Politècnica de Catalunya [Barcelona]
(2) Universitat Politècnica de Catalunya = Université polytechnique de Catalogne [Barcelona]
(3) Universitat Politècnica de Catalunya = Université polytechnique de Catalogne = Polytechnic University of Catalunya [Barcelona]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Proceedings
DOI
10.46298/dmtcs.3391
License
https://about.hal.science/hal-authorisation-v1
Indicators
747
Views
578
Downloads

Distance graphs with maximum chromatic number

Javier Barajas (1) (2) (3), Oriol Serra ORCID (1) (2) (3)
(1) Universitat Politècnica de Catalunya [Barcelona]
(2) Universitat Politècnica de Catalunya = Université polytechnique de Catalogne [Barcelona]
(3) Universitat Politècnica de Catalunya = Université polytechnique de Catalogne = Polytechnic University of Catalunya [Barcelona]
Abstract
Let $D$ be a finite set of integers. The distance graph $G(D)$ has the set of integers as vertices and two vertices at distance $d ∈D$ are adjacent in $G(D)$. A conjecture of Xuding Zhu states that if the chromatic number of $G (D)$ achieves its maximum value $|D|+1$ then the graph has a clique of order $|D|$. We prove that the chromatic number of a distance graph with $D=\{ a,b,c,d\}$ is five if and only if either $D=\{1,2,3,4k\}$ or $D=\{ a,b,a+b,a+2b\}$ with $a \equiv 0 (mod 2)$ and $b \equiv 1 (mod 2)$. This confirms Zhu's conjecture for $|D|=4$.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • Distance graphs
  • chromatic number
Cited by

Source: OpenCitations

  • On the independence ratio of distance graphs

    Discrete Mathematics

    Authors : James M. Carraher ORCID, David Galvin ORCID, Stephen G. Hartke ORCID, A.J. Radcliffe ORCID, Derrick Stolee ORCID

    Journal reference : Volume 339, 2016, pp. 3058-3072

    DOI : 10.1016/j.disc.2016.05.018

  • Solving Lonely Runner Conjecture through differential geometry

    Journal of Applied Mathematics Statistics and Informatics

    Authors : V. Ďuriš ORCID, T. Šumný, D. Gonda ORCID, T. Lengyelfalusy ORCID

    Journal reference : Volume 18, 2022, pp. 21-28

    DOI : 10.2478/jamsi-2022-0002

  • Maximal Density of Sets with Missing Differences and Various Coloring Parameters of Distance Graphs

    Taiwanese Journal of Mathematics

    Authors : Ram Krishna Pandey ORCID, Neha Rai ORCID

    Journal reference : Volume 24, 2020, pp.

    DOI : 10.11650/tjm/200403

  • On the chromatic number of integral circulant graphs

    Computers & Mathematics with Applications

    Authors : Aleksandar Ilić ORCID, Milan Bašić ORCID

    Journal reference : Volume 60, 2010, pp. 144-150

    DOI : 10.1016/j.camwa.2010.04.041

  • Regular chromatic number and the lonely runner problem

    Electronic Notes in Discrete Mathematics

    Authors : J. Barajas, O. Serra ORCID

    Journal reference : Volume 29, 2007, pp. 479-483

    DOI : 10.1016/j.endm.2007.07.085

  • Chromatic number of distance graphs generated by the sets {2,3,x,y}

    Journal of Combinatorial Optimization

    Authors : Daphne Der-Fen Liu ORCID, Aileen Sutedja

    Journal reference : Volume 25, 2012, pp. 680-693

    DOI : 10.1007/s10878-012-9509-4

  • The Lonely Runner Conjecture turns 60

    Computer Science Review

    Authors : Guillem Perarnau ORCID, Oriol Serra ORCID

    Journal reference : Volume 58, 2025, pp. 100798

    DOI : 10.1016/j.cosrev.2025.100798

  • Fractional Chromatic Numbers and Chromatic Numbers for the Fibonacci Distance Graphs

    The Fibonacci Quarterly

    Authors : Anshika Srivastava ORCID

    Journal reference : Volume 63, 2025, pp. 456-468

    DOI : 10.1080/00150517.2025.2503249

  • Packing Density of Sets With Only Two Nonmixed Gaps

    Journal of Graph Theory

    Authors : Alexander Natalchenko, Arsenii Sagdeev ORCID

    Journal reference : Volume 110, 2025, pp. 263-271

    DOI : 10.1002/jgt.23269

  • On the chromatic number of circulant graphs

    Discrete Mathematics

    Authors : Javier Barajas, Oriol Serra ORCID

    Journal reference : Volume 309, 2008, pp. 5687-5696

    DOI : 10.1016/j.disc.2008.04.041

  • Density of sets with missing differences and applications

    Mathematica Slovaca

    Authors : Ram Krishna Pandey ORCID, Neha Rai ORCID

    Journal reference : Volume 71, 2021, pp. 595-614

    DOI : 10.1515/ms-2021-0006

  • Packing chromatic number of distance graphs

    Discrete Applied Mathematics

    Authors : Jan Ekstein ORCID, Přemysl Holub ORCID, Bernard Lidický ORCID

    Journal reference : Volume 160, 2011, pp. 518-524

    DOI : 10.1016/j.dam.2011.11.022

  • On packing colorings of distance graphs

    Discrete Applied Mathematics

    Authors : Olivier Togni ORCID

    Journal reference : Volume 167, 2013, pp. 280-289

    DOI : 10.1016/j.dam.2013.10.026
Preview
Loading PDF preview...