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. (2023, June). Injective colouring for H-free graphs. Presented at CSR 2021, Sochi

• Presentation Conference Type: Conference Paper (published)
• Conference Name: CSR 2021
• 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
• Print ISSN: 0302-9743
• 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/