A note on selective line-graphs and partition colorings

Cornaz, Denis; Furini, Fabio; Malaguti, Enrico; Santini, Alberto

Cornaz, Denis; Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2019), A note on selective line-graphs and partition colorings, Operations Research Letters, 47, 6, p. 565-568. 10.1016/j.orl.2019.08.005

View/Open

CFMS-2019.pdf (55.90Kb)

Type

Article accepté pour publication ou publié

Date

2019

Journal name

Operations Research Letters

Volume

Number

Publisher

Elsevier

Pages

565-568

Publication identifier

10.1016/j.orl.2019.08.005

Metadata

Show full item record

Author(s)

Cornaz, Denis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Furini, Fabio
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Malaguti, Enrico
D.E.I. - University of Bologna.
Santini, Alberto

Abstract (EN)

We extend a one-to-one correspondence between the set of all colorings of any graph and the set of all stable sets of an auxiliary graph, from graphs to partitioned graphs. This correspondence has an application to Selective Coloring and to Selective Max-Coloring.

Subjects / Keywords

Selective/partition coloring; Line graph; Stable set; Max-coloring