Classifying k-Edge Colouring for H-free Graphs

Galby, E.; Lima, P.T.; Paulusma, D.; Ries, B.

doi:10.1016/j.ipl.2019.02.006

Classifying k-Edge Colouring for H-free Graphs

Galby, E.; Lima, P.T.; Paulusma, D.; Ries, B.

Authors

E. Galby

P.T. Lima

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

B. Ries

Abstract

A graph is H-free if it does not contain an induced subgraph isomorphic to H. For every integer k and every graph H, we determine the computational complexity of k-Edge Colouring for H-free graphs.

Citation

Galby, E., Lima, P., Paulusma, D., & Ries, B. (2019). Classifying k-Edge Colouring for H-free Graphs. Information Processing Letters, 146, 39-43. https://doi.org/10.1016/j.ipl.2019.02.006

Journal Article Type	Article
Acceptance Date	Feb 18, 2019
Online Publication Date	Feb 20, 2019
Publication Date	Jun 1, 2019
Deposit Date	Feb 22, 2019
Publicly Available Date	Feb 20, 2020
Journal	Information Processing Letters
Print ISSN	0020-0190
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
Volume	146
Pages	39-43
DOI	https://doi.org/10.1016/j.ipl.2019.02.006
Public URL	https://durham-repository.worktribe.com/output/1302469

Files

Accepted Journal Article (369 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/

Copyright Statement
© 2019 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/