The Complexity of Colouring by Semicomplete Digraphs

Jørgen Bang-Jensen; Pavol  Hell; Gary MacGillivray

doi:10.1137/0401029

The Complexity of Colouring by Semicomplete Digraphs

Jørgen Bang-Jensen
, Pavol Hell
, Gary MacGillivray

Institut for Matematik og Datalogi

University of Victoria

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

Abstract

The following problem, known as the H-colouring problem, is studied. An H-colouring of a directed graph D is a mapping $f:V( D ) \to V( H )$ such that $( f( x ),f( y ) )$ is an edge of H whenever $( x,y )$ is an edge of D. The H-colouring problem is the following. Instance: A directed graph D. Question: Does there exist an H-colouring of D? In this paper it is shown that for semicomplete digraphs T the T-colouring problem is NP-complete when T has more than one directed cycle, and polynomially decidable otherwise.

Originalsprog	Engelsk
Tidsskrift	SIAM Journal on Discrete Mathematics
Vol/bind	1
Udgave nummer	3
Sider (fra-til)	281–298
ISSN	0895-4801
DOI	https://doi.org/10.1137/0401029
Status	Udgivet - 1988

Dokumenter og links

10.1137/0401029

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

Citationsformater

@article{a7c9cf608d464151a6bab3864311320f,

title = "The Complexity of Colouring by Semicomplete Digraphs",

abstract = "The following problem, known as the H-colouring problem, is studied. An H-colouring of a directed graph D is a mapping \$f:V( D ) \textbackslash{}to V( H )\$ such that \$( f( x ),f( y ) )\$ is an edge of H whenever \$( x,y )\$ is an edge of D. The H-colouring problem is the following. Instance: A directed graph D. Question: Does there exist an H-colouring of D? In this paper it is shown that for semicomplete digraphs T the T-colouring problem is NP-complete when T has more than one directed cycle, and polynomially decidable otherwise.",

author = "J{\o}rgen Bang-Jensen and Pavol Hell and Gary MacGillivray",

year = "1988",

doi = "10.1137/0401029",

language = "English",

volume = "1",

pages = " 281–298",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics",

number = "3",

}

TY - JOUR

T1 - The Complexity of Colouring by Semicomplete Digraphs

AU - Bang-Jensen, Jørgen

AU - Hell, Pavol

AU - MacGillivray, Gary

PY - 1988

Y1 - 1988

N2 - The following problem, known as the H-colouring problem, is studied. An H-colouring of a directed graph D is a mapping $f:V( D ) \to V( H )$ such that $( f( x ),f( y ) )$ is an edge of H whenever $( x,y )$ is an edge of D. The H-colouring problem is the following. Instance: A directed graph D. Question: Does there exist an H-colouring of D? In this paper it is shown that for semicomplete digraphs T the T-colouring problem is NP-complete when T has more than one directed cycle, and polynomially decidable otherwise.

AB - The following problem, known as the H-colouring problem, is studied. An H-colouring of a directed graph D is a mapping $f:V( D ) \to V( H )$ such that $( f( x ),f( y ) )$ is an edge of H whenever $( x,y )$ is an edge of D. The H-colouring problem is the following. Instance: A directed graph D. Question: Does there exist an H-colouring of D? In this paper it is shown that for semicomplete digraphs T the T-colouring problem is NP-complete when T has more than one directed cycle, and polynomially decidable otherwise.

U2 - 10.1137/0401029

DO - 10.1137/0401029

M3 - Journal article

SN - 0895-4801

VL - 1

SP - 281

EP - 298

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -

The Complexity of Colouring by Semicomplete Digraphs

Abstract

Dokumenter og links

SDU link

Fingeraftryk

Citationsformater