Injective colouring for H-free graphs

Bok, J.; Jedličková, N.; Martin, B.; Paulusma, D.; Smith, S.

Injective colouring for H-free graphs

Bok, J.; Jedličková, N.; Martin, B.; Paulusma, D.; Smith, S.

Authors

J. Bok

N. Jedličková

Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor

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

Siani Alice Smith siani.smith@durham.ac.uk
PGR Student Doctor of Philosophy

Abstract

A function c : V (G) → {1, 2, . . . , k} is a k-colouring of a graph G if c(u) 6= c(v) whenever u and v are adjacent. If any two colour classes induce the disjoint union of vertices and edges, then c is called injective. Injective colourings are also known as L(1, 1)-labellings and distance 2-colourings. The corresponding decision problem is denoted Injective Colouring. A graph is H-free if it does not contain H as an induced subgraph. We prove a dichotomy for Injective Colouring for graphs with bounded independence number. Then, by combining known with further new results, we determine the complexity of Injective Colouring on H-free graphs for every H except for one missing case.

Citation

Bok, J., Jedličková, N., Martin, B., Paulusma, D., & Smith, S. (2021). Injective colouring for H-free graphs.

Conference Name	CSR 2021
Conference Location	Sochi
Start Date	Jun 28, 2023
End Date	Jul 2, 2021
Acceptance Date	Feb 8, 2021
Publication Date	Jun 28, 2021
Deposit Date	Feb 7, 2021
Publisher	Springer Verlag
Series Title	Lecture Notes in Computer Science
Series ISSN	0302-9743
Public URL	https://durham-repository.worktribe.com/output/1139723
Publisher URL	https://logic.pdmi.ras.ru/~csr/