List-k-Coloring H-Free Graphs for All k>4

Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl

doi:10.1007/s00493-024-00106-2

List-k-Coloring H-Free Graphs for All k>4

Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

Given an integer k>4 and a graph H, we prove that, assuming P≠NP, the List-k-Coloring Problem restricted to H-free graphs can be solved in polynomial time if and only if either every component of H is a path on at most three vertices, or removing the isolated vertices of H leaves an induced subgraph of the five-vertex path. In fact, the “if” implication holds for all k≥1.

Original language	English (US)
Pages (from-to)	1063-1068
Number of pages	6
Journal	Combinatorica
Volume	44
Issue number	5
DOIs	https://doi.org/10.1007/s00493-024-00106-2
State	Published - Oct 2024

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Keywords

Coloring
Induced subgraphs
List-Coloring
Polynomial-time Algorithms

Access to Document

10.1007/s00493-024-00106-2

Cite this

@article{72c8a64f46e848eeb933035827602e06,

title = "List-k-Coloring H-Free Graphs for All k>4",

abstract = "Given an integer k>4 and a graph H, we prove that, assuming P≠NP, the List-k-Coloring Problem restricted to H-free graphs can be solved in polynomial time if and only if either every component of H is a path on at most three vertices, or removing the isolated vertices of H leaves an induced subgraph of the five-vertex path. In fact, the “if” implication holds for all k≥1.",

keywords = "Coloring, Induced subgraphs, List-Coloring, Polynomial-time Algorithms",

author = "Maria Chudnovsky and Sepehr Hajebi and Sophie Spirkl",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive licence to J{\'a}nos Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature 2024.",

year = "2024",

month = oct,

doi = "10.1007/s00493-024-00106-2",

language = "English (US)",

volume = "44",

pages = "1063--1068",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "5",

}

TY - JOUR

T1 - List-k-Coloring H-Free Graphs for All k>4

AU - Chudnovsky, Maria

AU - Hajebi, Sepehr

AU - Spirkl, Sophie

N1 - Publisher Copyright: © The Author(s), under exclusive licence to János Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature 2024.

PY - 2024/10

Y1 - 2024/10

N2 - Given an integer k>4 and a graph H, we prove that, assuming P≠NP, the List-k-Coloring Problem restricted to H-free graphs can be solved in polynomial time if and only if either every component of H is a path on at most three vertices, or removing the isolated vertices of H leaves an induced subgraph of the five-vertex path. In fact, the “if” implication holds for all k≥1.

AB - Given an integer k>4 and a graph H, we prove that, assuming P≠NP, the List-k-Coloring Problem restricted to H-free graphs can be solved in polynomial time if and only if either every component of H is a path on at most three vertices, or removing the isolated vertices of H leaves an induced subgraph of the five-vertex path. In fact, the “if” implication holds for all k≥1.

KW - Coloring

KW - Induced subgraphs

KW - List-Coloring

KW - Polynomial-time Algorithms

UR - http://www.scopus.com/inward/record.url?scp=85193025043&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85193025043&partnerID=8YFLogxK

U2 - 10.1007/s00493-024-00106-2

DO - 10.1007/s00493-024-00106-2

M3 - Article

AN - SCOPUS:85193025043

SN - 0209-9683

VL - 44

SP - 1063

EP - 1068

JO - Combinatorica

JF - Combinatorica

IS - 5

ER -

List-k-Coloring H-Free Graphs for All k>4

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this