Injective Colouring for H-Free Graphs

Jan Bok; Nikola Jedličková; Barnaby Martin; Daniël Paulusma; Siani Smith

doi:10.1007/978-3-030-79416-3_2

Injective Colouring for H-Free Graphs

Jan Bok
, Nikola Jedličková
, Barnaby Martin
, Daniël Paulusma
, Siani Smith^*

^*Corresponding author for this work

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

3 Citations (Scopus)

Abstract

A function c: V(G) → { 1, 2, …, k} is a k-colouring of a graph G if c(u) ≠ 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.

Original language	English
Title of host publication	Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings
Editors	Rahul Santhanam, Daniil Musatov
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	18-30
Number of pages	13
ISBN (Electronic)	9783030794163
ISBN (Print)	9783030794156
DOIs	https://doi.org/10.1007/978-3-030-79416-3_2
Publication status	Published - 17 Jun 2021
Event	16th International Computer Science Symposium in Russia, CSR 2021 - Sochi, Russian Federation Duration: 28 Jun 2021 → 2 Jul 2021 https://logic.pdmi.ras.ru/csr2021/

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12730 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Computer Science Symposium in Russia, CSR 2021
Country/Territory	Russian Federation
City	Sochi
Period	28/06/21 → 2/07/21
Internet address	https://logic.pdmi.ras.ru/csr2021/

Bibliographical note

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Access to Document

10.1007/978-3-030-79416-3_2Licence: Unspecified

Handle.net

Persistent link

Cite this

Bok, J., Jedličková, N., Martin, B., Paulusma, D., & Smith, S. (2021). Injective Colouring for H-Free Graphs. In R. Santhanam, & D. Musatov (Eds.), Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings (pp. 18-30). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12730 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-79416-3_2

Bok, Jan ; Jedličková, Nikola ; Martin, Barnaby et al. / Injective Colouring for H-Free Graphs. Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings. editor / Rahul Santhanam ; Daniil Musatov. Springer Science and Business Media Deutschland GmbH, 2021. pp. 18-30 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7faffd331d9d4873bfd0195160fccf3d,

title = "Injective Colouring for H-Free Graphs",

abstract = "A function c: V(G) → \{ 1, 2, …, k\} is a k-colouring of a graph G if c(u) ≠ 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.",

author = "Jan Bok and Nikola Jedli{\v c}kov{\'a} and Barnaby Martin and Dani{\"e}l Paulusma and Siani Smith",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 16th International Computer Science Symposium in Russia, CSR 2021 ; Conference date: 28-06-2021 Through 02-07-2021",

year = "2021",

month = jun,

day = "17",

doi = "10.1007/978-3-030-79416-3\_2",

language = "English",

isbn = "9783030794156",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "18--30",

editor = "Rahul Santhanam and Daniil Musatov",

booktitle = "Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings",

address = "Germany",

url = "https://logic.pdmi.ras.ru/csr2021/",

}

Bok, J, Jedličková, N, Martin, B, Paulusma, D & Smith, S 2021, Injective Colouring for H-Free Graphs. in R Santhanam & D Musatov (eds), Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12730 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 18-30, 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russian Federation, 28/06/21. https://doi.org/10.1007/978-3-030-79416-3_2

Injective Colouring for H-Free Graphs. / Bok, Jan; Jedličková, Nikola; Martin, Barnaby et al.
Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings. ed. / Rahul Santhanam; Daniil Musatov. Springer Science and Business Media Deutschland GmbH, 2021. p. 18-30 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12730 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - Injective Colouring for H-Free Graphs

AU - Bok, Jan

AU - Jedličková, Nikola

AU - Martin, Barnaby

AU - Paulusma, Daniël

AU - Smith, Siani

PY - 2021/6/17

Y1 - 2021/6/17

N2 - A function c: V(G) → { 1, 2, …, k} is a k-colouring of a graph G if c(u) ≠ 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.

AB - A function c: V(G) → { 1, 2, …, k} is a k-colouring of a graph G if c(u) ≠ 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.

UR - https://www.scopus.com/pages/publications/85111815315

U2 - 10.1007/978-3-030-79416-3_2

DO - 10.1007/978-3-030-79416-3_2

M3 - Conference Contribution (Conference Proceeding)

AN - SCOPUS:85111815315

SN - 9783030794156

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 18

EP - 30

BT - Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings

A2 - Santhanam, Rahul

A2 - Musatov, Daniil

PB - Springer Science and Business Media Deutschland GmbH

T2 - 16th International Computer Science Symposium in Russia, CSR 2021

Y2 - 28 June 2021 through 2 July 2021

ER -

Bok J, Jedličková N, Martin B, Paulusma D, Smith S. Injective Colouring for H-Free Graphs. In Santhanam R, Musatov D, editors, Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2021. p. 18-30. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-79416-3_2

Injective Colouring for H-Free Graphs

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this