On distance graph coloring problems

• Published date: 01 May 2021
• Author: Jayme Szwarcfiter,Rosiane de Freitas,Bruno Dias,Nelson Maculan
• DOI: http://doi.org/10.1111/itor.12626
• Date: 01 May 2021

Intl. Trans. in Op. Res. 28 (2021) 1213–1241

DOI: 10.1111/itor.12626

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

On distance graph coloring problems

Rosiane de Freitasa,∗, Bruno Diasa, Nelson Maculanband

Jayme Szwarcfiterb

aPrograma de P´

os-Graduac¸˜

ao em Inform´

atica, Instituto de Computac¸˜

ao, Universidade Federaldo Amazonas, Av. Rodrigo

Ot´

avio 3000, 69000-000 Manaus, Brazil

bPrograma de Engenharia de Sistemas e Computac¸˜

ao, COPPE, Universidade Federaldo Rio de Janeiro, C.P. 68530,

21945-970 Rio de Janeiro, Brazil

E-mail: rosiane@icomp.ufam.edu.br[de Freitas]; bruno.dias@icomp.ufam.edu.br [Dias];

maculan@cos.ufrj.br [Maculan]; jayme@cos.ufrj.br [Szwarcfiter]

Received 30 August2018; received in revised form 25 December 2018; accepted 27 December 2018

Abstract

One of the most important classes of combinatorial optimization problems is graph coloring, and there are

several variations of this general problem involving additional constraints either on vertices or edges. They

constitute models for real applications, such as channel assignment in mobile wireless networks. In this work,

we consider some coloring problems involving distance constraints as weighted edges, modeling them as

distance geometry problems (DGPs). Thus, the vertices of the graph are considered as embedded on the

real line and the coloring is treated as an assignment of positive integers to the vertices, while the distances

correspond to line segments, where the goal is to find their feasible intersection. We formulate these coloring

problem variants and show feasibility conditions for some problems. We also propose implicit enumeration

methods for some of the optimization problems based on branch-and-prune algorithms proposed for DGPs

in the literature. An empirical analysis was undertaken, considering equality and inequality constraints, and

uniform and arbitrary set of distances. As the main contributions, we propose new variations of vertex

coloring problems in graphs, involving a new theoreticalmodel in distance geometry (DG) for vertex coloring

problems with generalized adjacency constraints, promoting the correlation between graph theory and DG

fields. We also give a characterization and formal proof of polynomial cases for special graph classes, since

the general main problem is NP-complete.

Keywords:algorithms; bandwidth coloring; computational complexity; distance geometry; graph theory; T-coloring

1. Introduction

Let G=(V,E)be an undirected graph. A k-coloring of Gis an assignment of colors {1,2,...,k}

to the vertices of Gso that no two adjacent vertices share the same color. The chromatic number

χGof a graph is the minimum value of kfor which Gis k-colorable. The classic graph coloring

∗Corresponding author.

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

1214 R. de Freitas et al. / Intl. Trans.in Op. Res. 28 (2021) 1213–1241

problem, which consists in finding the chromatic number of a graph, is one of the most important

combinatorial optimization problems and it is known to be NP-hard (Karp, 1972).

There are several versionsof this classic vertex coloring problem, involving additional constraints,

in both edges as vertices of the graph, with a number of practical applications as well as theoretical

challenges (Hale, 1980; Malaguti and Toth, 2010; Lai and Lu, 2013; Bordini et al., 2019). One of

the main applications of such problems consists of assigning channels to transmitters in a mobile

wireless network. Each transmitter is responsible for the calls made in the area it covers, and the

communication among devices is made through a channel consisting of a discrete slice of the

electromagnetic spectrum. However, the channels cannot be assigned to calls in an arbitrary way,

since there is the problem of interference among devices located near each other using approximate

channels. There are three main types of interferences: co-channel, among calls of two transmitters

using the same channels; adjacent channel, among calls of two transmitters using adjacent channels;

and co-site, among calls on the same cell that do not respect a minimal separation. It is necessary to

assign channels to the calls such that interference is avoided and the spectrum usage is minimized

(Koster, 1999; Koster and Mu˜

noz, 2010; Audhya et al., 2011).

Thus, the channel assignment scenario is modeled as a graph coloring problem by considering

each transmitter as a vertex in an undirected graph,and the channels to be assigned as the colors that

the vertices will receive.Some more general graph coloring problems were proposed in the literature

in order to take the separation among channels into account, such as the T-coloring problem, also

known as the generalized coloring problem where, for each edge, the absolute difference between

colors assigned to each vertex must not be in a given forbidden set (Hale, 1980). Also,the bandwidth

coloring problem (BCP), a special case of T-coloring where the absolute difference between colors

assigned to each vertex must be greater than or equal to a certain value (Malaguti and Toth, 2010;

Lai and Lu, 2013; Dias et al., 2016), and the coloring problem with restrictions of adjacent colors

(COLRAC), where there is a restriction graph for which adjacent colors in it cannot be assigned to

adjacent vertices (Akihiro et al., 2002).

The separation among channels is a type of distance constraint, so we can model the channel

assignment scenario using distance geometry (DG) concepts (Liberti et al., 2014) since we have to

place the channels in the transmitters respecting some distances imposed in the edges, as can be

seen in Fig. 1. In the distance geometry problem (DGP), we are given an integer n>0 and a simple

undirected graph G=(V,E),where,foreach(i,j)∈E, there is a value di,jand we must determine

whether there is a mapping x:V→Rnsuch that ∀(i,j)∈Ex(i)−x(j)=di,j.

One method to solve DGP with discrete is the branch-and-prune (BP) approach proposed by

(Lavor et al., 2012a, 2012b), where a solution is built, and if at some point a distance constraint is

violated, then we stop this construction (prune) and try another option for the current solution in

the search space (see also Lavor et al., 2012a; Mucherino et al., 2012, 2013; Dias, 2014; de Freitas

et al., 2016).

The main contribution of this paper consists of a DG approach for special cases of T-coloring

problems with distance constraints, involving a study of graph classes for which some of these dis-

tance coloring problems are unfeasible, and branch-prune-and-bound (BPB) algorithms, combining

concepts from the branch-and-bound method and constraint propagation, for the considered prob-

lems.

The remainder of this paper is organized as follows. Section 2 defines the DG models for some

special graph coloring problems. Section 3 shows some properties regarding the structure of those

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies