We study colorings of Euclidean spaces avoiding specified patterns on straight lines. This extends the seminal work of Thue on avoidability properties of sequences to continuous, higher dimensional structures. We prove that every space $\mathbb{R}^d$ has a $2$-coloring such that no sequence of colors derived from collinear points separated by unit distance consists of more than $r(d)$ identical blocks. In case of the plane we show that $r(2)\leqslant 43$. We also consider more general patterns and give a sufficient condition for a pattern to be avoided in the plane. This supports a general Pattern Avoidance Conjecture in Euclidean spaces. The proofs are based mainly on the probabilistic method, but additional tools are forced by the geometric nature of the problem. We also consider similar questions for general geometric graphs in the plane. In the conclusion of the paper, we pose several conjectures alluding to some famous open problems in Euclidean Ramsey Theory.

In this paper we give a family of online algorithms for the classical coloring and the $L(2,1)$-labeling problems of unit disk intersection graphs. In the $L(2,1)$-labeling we ask for an assignment of nonnegative integers to the vertices of the input graph, such that adjacent vertices get labels that differ by at least 2, and vertices with a common neighbor get different labels. In particular, we present a coloring algorithm with competitive ratio less than 5, which makes it the currently best online coloring algorithm for unit disk intersection graphs. Our algorithms make use of a geometric representation of such graphs and are inspired by previous results but have better competitive ratios. The improvement comes from a novel application of a fractional and a $b$-fold coloring of the plane, which is in turn a variation of the Hadwiger--Nelson problem. Our method can also be adapted successfully for other classes of geometric intersection graphs.

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 $$\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]}) \geqslant 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 $$\chi _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]} \leqslant 4.36$$ ) for the fractional coloring of graphs $$G_{[a,b]}$$ , obtaining a bound dependent on $$\frac{a}{b}$$ . 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 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.