Fractional and j-fold coloring of the plane

DOI10.1007/S00454-016-9769-3zbMATH Open1338.05082arXiv1506.01887OpenAlexW2280133675WikidataQ59472682 ScholiaQ59472682MaRDI QIDQ282745FDOQ282745

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

Publication date: 12 May 2016

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We present results referring to the Hadwiger-Nelson problem which asks for the minimum number of colours needed to colour the plane with no two points at distance $1$ having the same colour. Exoo considered a more general problem concerning graphs $G_{[a,b]}$ with $mathbb{R}^2$ as the vertex set and two vertices adjacent if their distance is in the interval $[a,b]$. Exoo conjectured $chi(G_{[a,b]})=7$ for sufficiently small but positive difference between $a$ and $b$. We partially answer this conjecture by proving that $chi(G_{[a,b]})geq5$ for $b>a$. A $j$-fold colouring of graph $G=(V,E)$ is an assignment of $j$-elemental sets of colours to the vertices of $G$, in such a way that the sets assigned to any two adjacent vertices are disjoint. The fractional chromatic number $ch{i}_f(G)$ is the infimum of fractions $k/j$ for $j$-fold colouring of $G$ using $k$ colours. We generalize a method by Hochberg and O'Donnel (who proved that $G_{[1,1]}leq4.36$) for fractional colouring of graphs $G_{[a,b]}$, obtaining a bound dependant on $fracab$. We also 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 colouring 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.

Full work available at URL: https://arxiv.org/abs/1506.01887

Recommendations

• Coloring distance graphs on the plane
• The fractional chromatic number of the plane
• scientific article; zbMATH DE number 1552837
• Colouring proximity graphs in the plane
• The Hadwiger-Nelson problem with two forbidden distances

zbMATH Keywords

coloring of the planefractional coloringHadwiger-Nelson problem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• The realization of distances in measurable subsets covering \(R^ n\).
• Approximating monochromatic triangles in a two-colored plane
• \(\varepsilon\)-unit distance graphs
• Die Kugel als Körper extremaler Korona
• On the Chromatic Numbers of and with Intervals of Forbidden Distances
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (9)

• On the chromatic number of an infinitesimal plane layer
• Finite \(\epsilon\)-unit distance graphs
• Title not available (Why is that?)
• The fractional chromatic number of the plane
• Upper bound on the circular chromatic number of the plane
• Fractional coloring of triangle-free planar graphs
• Coloring distance graphs on the plane
• Online coloring of disk graphs
• Online coloring and \(L(2,1)\)-labeling of unit disk intersection graphs

This page was built for publication: Fractional and \(j\)-fold coloring of the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q282745)