Fractional and j-fold colouring of the plane

Jarosław Grytczuk , Konstanty Junosza-Szaniawski , Joanna Sokół , Krzysztof Węsek

Abstract

We present results referring to the Hadwiger–Nelson problem which asks for the minimum number of colors needed to color the plane with no two points at distance 1 having the same color. Exoo considered a more general problem concerning graphs G[a,b] with R2 as the vertex set and two vertices adjacent if their distance is in the interval [a,b]. Exoo conjectured χ(G[a,b]) = 7 for sufficiently small but positive difference between a and b. We partially answer this conjecture by proving that χ(G[a,b]) 5 for b > a. A j-fold coloring of a graph G = (V,E) is an assignment of j-elemental sets of colors to the vertices of G, in such a way that the sets assigned to any two adjacent vertices are disjoint. The fractional chromatic number χf (G) is the infimum of fractions k/j for j-fold coloring of G using k colors. We generalize a method by Hochberg and O’Donnel (who proved that G[1,1] 4.36) for the fractional coloring of graphs G[a,b], obtaining a bound dependent on a . We also b present few specific and two general methods for j-fold coloring of G[a,b] for small j, in particular for G[1,1] and G[1,2]. The j-fold coloring for small j has strong practical motivation especially in scheduling theory, while graph G[1,2] is often used to model hidden conflicts in radio networks.
Author Jarosław Grytczuk ZAK
Jarosław Grytczuk,,
- Department of Algebra and Combinatorics
, Konstanty Junosza-Szaniawski ZAK
Konstanty Junosza-Szaniawski,,
- Department of Algebra and Combinatorics
, Joanna Sokół WMiNI
Joanna Sokół,,
- Faculty of Mathematics and Information Science
, Krzysztof Węsek WMiNI
Krzysztof Węsek,,
- Faculty of Mathematics and Information Science
Journal seriesDiscrete & Computational Geometry, ISSN 0179-5376
Issue year2016
Vol55
No3
Pages594-609
Publication size in sheets0.75
Keywords in EnglishFractional coloring, Hadwiger–Nelson problem, Coloring of the plane
Abstract in PolishWyniki własne dotyczące kolorowania klasycznego i ułamkowego grafów G_[a,b] na płaszczyźnie, tj. w których zbiór wierzchołków to zbiór punktów płaszczyzny, a krawędź istnieje między wierzchołkami w odległości od a do b (dla pewnych liczb dodatnich a i b). W pracy pokazano, że dla każdego b>a liczba chromatyczna takiego grafu wynosi co najmniej 5. Większość wyników to sposoby ułamkowego kolorowania grafów G_a,b$ w zależności od parametrów a i b: po pierwsze górne oszacowanie na ułamkową liczbę chromatyczną, po drugie sposoby kolorowania przy małej liczbie warstw kolorów, które ma mocne motywacje w zastosowaniach telekomunikacyjnych.
DOIDOI:10.1007/s00454-016-9769-3
URL http://rd.springer.com/article/10.1007%2Fs00454-016-9769-3
Languageen angielski
Score (nominal)30
ScoreMinisterial score = 30.0, 28-11-2017, ArticleFromJournal
Ministerial score (2013-2016) = 30.0, 28-11-2017, ArticleFromJournal
Publication indicators WoS Impact Factor: 2016 = 0.724 (2) - 2016=0.914 (5)
Citation count*0
Cite
Share Share



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