Graph coloring and Graham′s greatest common divisor problem

Bartłomiej Bosek , Michał Dębski , Jarosław Grytczuk , Joanna Sokół , Małgorzata Śleszyńska-Nowak , Wiktor Żelazny

Abstract

In this paper we introduce and study two graph coloring problems and relate them to some deep number-theoretic problems. For a fixed positive integer k consider a graph B_k whose vertex set is the set of all positive integers with two vertices a, b joined by an edge whenever the two numbers a/gcd(a, b) and b/gcd(a, b) are both at most k. We conjecture that the chromatic number of every such graph B_k is equal to k. This would generalize the greatest common divisor problem of Graham from 1970; in graph-theoretic terminology it states that the clique number of Bk is equal to k. Our conjecture is connected to integer lattice tilings and partial Latin squares completions.
Author Bartłomiej Bosek
Bartłomiej Bosek,,
-
, Michał Dębski (FMIS / DAC)
Michał Dębski,,
- Department of Algebra and Combinatorics
, Jarosław Grytczuk (FMIS / DAC)
Jarosław Grytczuk,,
- Department of Algebra and Combinatorics
, Joanna Sokół (FMIS)
Joanna Sokół,,
- Faculty of Mathematics and Information Science
, Małgorzata Śleszyńska-Nowak (FMIS / DIPS)
Małgorzata Śleszyńska-Nowak,,
- Department of Information Processing Systems
, Wiktor Żelazny
Wiktor Żelazny,,
-
Journal seriesDiscrete Mathematics, ISSN 0012-365X, (A 25 pkt)
Issue year2018
Vol341
No3
Pages781-785
Publication size in sheets0.5
Keywords in PolishKolorowanie; problem Grahama
Keywords in EnglishColoring; Graham’s problem
ASJC Classification2607 Discrete Mathematics and Combinatorics; 2614 Theoretical Computer Science
Abstract in PolishW pracy badamy dwa problemy kolorowania grafów i pokazujemy ich związek z teorią liczb. Dla ustalonej liczby naturalnej k przez B_k oznaczamy graf na liczbach naturalnych, w którym wierzchołki a, b są połączone krawędzią gdy obie liczby a/nwd(a,b) i b/nwd(a,b) są nie większe niż k. Formułujemy hipotezę, że zawsze liczba chromatyczne B_k jest równa k. Stanowiłoby to uogólnienie problemu Grahama z roku 1970, w terminologii grafowej mówi on, że liczba klikowa grafu B_k jest równa k. Nasza hipoteza jest powiązana z podziałami krat liczbowych (ang. integer lattice tilings) i uzupełnianiem częściowych kwadratów łacińskich.
DOIDOI:10.1016/j.disc.2017.11.006
URL https://www.sciencedirect.com/science/article/pii/S0012365X17303898
Languageen angielski
Score (nominal)25
ScoreMinisterial score = 25.0, 11-03-2019, ArticleFromJournal
Ministerial score (2013-2016) = 25.0, 11-03-2019, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.005; WoS Impact Factor: 2017 = 0.738 (2) - 2017=0.796 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back