Injective colouring for H-free graphs

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

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
• Publisher URL: https://logic.pdmi.ras.ru/~csr/