The Complexity of Colouring by Semicomplete Digraphs
Authors:
- Jørgen Bang-JensenJBJørgen Bang-Jensen
- Pavol HellPHPavol Hell
- Gary MacGillivrayGMGary MacGillivray
- 2 August 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 1 (3) , 281-298
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.
Keywords
This publication has 5 references indexed in Scilit:
- On multiplicative graphs and the product conjectureCombinatorica, 1988
- On unavoidable digraphs in orientations of graphsJournal of Graph Theory, 1987
- On the complexity of the general coloring problemInformation and Control, 1981
- On classes of relations and graphs determined by subobjects and factorobjectsDiscrete Mathematics, 1978
- Graph Theory with Applications1976