Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
The NP-completeness of (1,r)-subcolorability of cubic graphs
Autore:
Le, HO; Le, VB;
Indirizzi:
Univ Rostock, Fachbereich Informat, D-18051 Rostock, Germany Univ RostockRostock Germany D-18051 Informat, D-18051 Rostock, Germany
Titolo Testata:
INFORMATION PROCESSING LETTERS
fascicolo: 3, volume: 81, anno: 2002,
pagine: 157 - 162
SICI:
0020-0190(20020214)81:3<157:TNO(OC>2.0.ZU;2-0
Fonte:
ISI
Lingua:
ENG
Keywords:
cubic graph; planar graph; subcoloring; computational complexity; combinatorial problem;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
6
Recensione:
Indirizzi per estratti:
Indirizzo: Le, VB Univ Rostock, Fachbereich Informat, D-18051 Rostock, Germany Univ Rostock Rostock Germany D-18051 at, D-18051 Rostock, Germany
Citazione:
H.O. Le e V.B. Le, "The NP-completeness of (1,r)-subcolorability of cubic graphs", INF PROCESS, 81(3), 2002, pp. 157-162

Abstract

A partition of the vertices of a graph G into k pairwise disjoint sets V-1,..., V-k is called an (r(l),..., r(k))-subcoloring if the subgraph Gi of Ginduced by Vi, 1 less than or equal to i less than or equal to k, consistsof disjoint complete subgraphs. each of which has cardinality no more thanri. Due to Erdos and Albertson et al., independently, every cubic (i.e., 3-regular) graph has a (2,2)-subcoloring. Albertson et al. then asked for cubic graphs having (1, 2)-subcolorings. We point out in this paper that thisquestion is algorithmically difficult by showing that recognizing (1, 2)-subcolorable cubic graphs is NP-complete, even when restricted to triangle-free planar graphs. (C) 2002 Elsevier Science B.V. All rights reserved.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 28/01/20 alle ore 15:05:19