ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


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


Konstanty Junosza-Szaniawski

Warsaw University of Technology
Pl. Politechniki 1, 00-661 Warsaw, Poland

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