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 - [Uniwersytet Jagiellonski w Krakowie]
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 - [Uniwersytet Jagiellonski w Krakowie]
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, 23-09-2019, ArticleFromJournal
Publication indicators Scopus Citations = 0; WoS Citations = 0; 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