Discussiones Mathematicae Graph Theory 25(1-2) (2005)
219

doi: 10.7151/dmgt.1275

## COLORING OF G^{2}∖G, FOR EUCLIDESIAN GRAPH G

Konstanty Junosza-Szaniawski

*Warsaw University of Technology*

*Pl. Politechniki 1, 00-661 Warsaw, Poland*

**e-mail:** k.szaniawski@mini.pw.edu.pl

The problem appeared in telecommunication.

Graph G = (V(G),E(G)) is called *Euclidean* if and only if V(G) is
a finite subset of R^{2} and {x,y} ∈ E(G) if and only if
dist(x,y) ≤ d, where d ∈ R is fixed.
Let S(G) = G^{2}∖G e.g. The vertex set of S(G) is V(G) and there is an edge
{x,y} in E(S(G)) if and only if {x,y} ∉ E(G) and
x,y have a common neighbor in G. We consider vertex coloring
of the graphs S(G), where G are Euclidean.

**Problem 1** **. **
Is there a polynomial algorithm, which gives the chromatic number
of S(G) for Euclidean graph G.

The problem appeared in telecommunication. In practical
applications standard approximate algorithms are used, but they do
not use the geometric properties of S(G) and they seem not to be
the most effective.

For geometric reasons χ
(S(G)) ≤ 12, where G is Euclidean,
but on other hand it is difficulty to find Euclidean graph G
such that χ(S(G)) > 6.

Received 21 November 2003