List 3-coloring Pt-free graphs with no induced 1-subdivision of K1,s

Maria Chudnovsky; Sophie Spirkl; Mingxian Zhong

doi:10.1016/j.disc.2020.112086

List 3-coloring P_t-free graphs with no induced 1-subdivision of K_1,s

Maria Chudnovsky
, Sophie Spirkl
, Mingxian Zhong

Mathematics

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

9 Scopus citations

Abstract

Let s and t be positive integers. We use P_t to denote the path with t vertices and K_1,s to denote the complete bipartite graph with parts of size 1 and s respectively. The one-subdivision of K_1,s is obtained by replacing every edge {u,v} of K_1,s by two edges {u,w} and {v,w} with a new vertex w. In this paper, we give a polynomial-time algorithm for the list 3-coloring problem restricted to the class of P_t-free graph with no induced 1-subdivision of K_1,s.

Original language	English (US)
Article number	112086
Journal	Discrete Mathematics
Volume	343
Issue number	11
DOIs	https://doi.org/10.1016/j.disc.2020.112086
State	Published - Nov 2020

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Keywords

Coloring
Dominating set
Forbidden induced subgraphs

Access to Document

10.1016/j.disc.2020.112086

Cite this

@article{7fe68490862c48a5baa741312733253e,

title = "List 3-coloring Pt-free graphs with no induced 1-subdivision of K1,s",

abstract = "Let s and t be positive integers. We use Pt to denote the path with t vertices and K1,s to denote the complete bipartite graph with parts of size 1 and s respectively. The one-subdivision of K1,s is obtained by replacing every edge \{u,v\} of K1,s by two edges \{u,w\} and \{v,w\} with a new vertex w. In this paper, we give a polynomial-time algorithm for the list 3-coloring problem restricted to the class of Pt-free graph with no induced 1-subdivision of K1,s.",

keywords = "Coloring, Dominating set, Forbidden induced subgraphs",

author = "Maria Chudnovsky and Sophie Spirkl and Mingxian Zhong",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2020",

month = nov,

doi = "10.1016/j.disc.2020.112086",

language = "English (US)",

volume = "343",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "11",

}

TY - JOUR

T1 - List 3-coloring Pt-free graphs with no induced 1-subdivision of K1,s

AU - Chudnovsky, Maria

AU - Spirkl, Sophie

AU - Zhong, Mingxian

PY - 2020/11

Y1 - 2020/11

N2 - Let s and t be positive integers. We use Pt to denote the path with t vertices and K1,s to denote the complete bipartite graph with parts of size 1 and s respectively. The one-subdivision of K1,s is obtained by replacing every edge {u,v} of K1,s by two edges {u,w} and {v,w} with a new vertex w. In this paper, we give a polynomial-time algorithm for the list 3-coloring problem restricted to the class of Pt-free graph with no induced 1-subdivision of K1,s.

AB - Let s and t be positive integers. We use Pt to denote the path with t vertices and K1,s to denote the complete bipartite graph with parts of size 1 and s respectively. The one-subdivision of K1,s is obtained by replacing every edge {u,v} of K1,s by two edges {u,w} and {v,w} with a new vertex w. In this paper, we give a polynomial-time algorithm for the list 3-coloring problem restricted to the class of Pt-free graph with no induced 1-subdivision of K1,s.

KW - Coloring

KW - Dominating set

KW - Forbidden induced subgraphs

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

UR - https://www.scopus.com/pages/publications/85089079693#tab=citedBy

U2 - 10.1016/j.disc.2020.112086

DO - 10.1016/j.disc.2020.112086

M3 - Article

AN - SCOPUS:85089079693

SN - 0012-365X

VL - 343

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 11

M1 - 112086

ER -