On the complexity of H-colouring planar graphs

G. MacGillivray; M. Siggers

doi:10.1016/j.disc.2008.05.016

On the complexity of H-colouring planar graphs

G. MacGillivray, M. Siggers

University of Victoria BC

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

We show that if H is an odd-cycle, or any non-bipartite graph of girth 5 and maximum degree at most 3, then planar H-COL is N P-complete.

Original language	English
Pages (from-to)	5729-5738
Number of pages	10
Journal	Discrete Mathematics
Volume	309
Issue number	18
DOIs	https://doi.org/10.1016/j.disc.2008.05.016
State	Published - 28 Sep 2009

Keywords

Graph homomorphism
H-colouring
NP-completeness
Planar graph

Access to Document

10.1016/j.disc.2008.05.016

Cite this

@article{f9fa6ec37d5e491d9a42e2a4249ccfe9,

title = "On the complexity of H-colouring planar graphs",

abstract = "We show that if H is an odd-cycle, or any non-bipartite graph of girth 5 and maximum degree at most 3, then planar H-COL is N P-complete.",

keywords = "Graph homomorphism, H-colouring, NP-completeness, Planar graph",

author = "G. MacGillivray and M. Siggers",

year = "2009",

month = sep,

day = "28",

doi = "10.1016/j.disc.2008.05.016",

language = "English",

volume = "309",

pages = "5729--5738",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "18",

}

TY - JOUR

T1 - On the complexity of H-colouring planar graphs

AU - MacGillivray, G.

AU - Siggers, M.

PY - 2009/9/28

Y1 - 2009/9/28

N2 - We show that if H is an odd-cycle, or any non-bipartite graph of girth 5 and maximum degree at most 3, then planar H-COL is N P-complete.

AB - We show that if H is an odd-cycle, or any non-bipartite graph of girth 5 and maximum degree at most 3, then planar H-COL is N P-complete.

KW - Graph homomorphism

KW - H-colouring

KW - NP-completeness

KW - Planar graph

UR - https://www.scopus.com/pages/publications/69549138386

U2 - 10.1016/j.disc.2008.05.016

DO - 10.1016/j.disc.2008.05.016

M3 - Article

AN - SCOPUS:69549138386

SN - 0012-365X

VL - 309

SP - 5729

EP - 5738

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 18

ER -

On the complexity of H-colouring planar graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this