Discussiones Mathematicae Graph Theory 25(1-2) (2005) 219
DOI: https://doi.org/10.7151/dmgt.1275

COLORING OF G²∖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² and {x,y} ∈ E(G) if and only if dist(x,y) ≤ d, where d ∈ R is fixed. Let S(G) = G²∖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