Skip to main content

Research Repository

Advanced Search

Injective colouring for H-free graphs

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


J. Bok

N. Jedličková


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.


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
Publisher URL