We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Injective colouring for H-free graphs

Bok, J. and Jedličková, N. and Martin, B. and Paulusma, D. and Smith, S. (2021) 'Injective colouring for H-free graphs.', CSR 2021 Sochi, 28 Jun - 02 Jul 2021.


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.

Item Type:Conference item (Paper)
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
Available under License - Creative Commons Attribution.
File format - PDF
Publisher Web site:
Date accepted:08 February 2021
Date deposited:16 April 2021
Date of first online publication:2021
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar