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

6 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 = "Funding Information: This paper is partially supported by National Science Foundation, United States of America grant DMS-1763817, U.S. Army Research Office grant W911NF-16-1-0404 and PSC-CUNY Award 3407-00 51, and is based upon work supported by the National Science Foundation, United States of America under Award No. DMS-1802201. Funding Information: This paper is partially supported by National Science Foundation, United States of America grant DMS-1763817 , U.S. Army Research Office grant W911NF-16-1-0404 and PSC-CUNY Award 3407-00 51, and is based upon work supported by the National Science Foundation, United States of America under Award No. DMS-1802201 . 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",

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

N1 - Funding Information: This paper is partially supported by National Science Foundation, United States of America grant DMS-1763817, U.S. Army Research Office grant W911NF-16-1-0404 and PSC-CUNY Award 3407-00 51, and is based upon work supported by the National Science Foundation, United States of America under Award No. DMS-1802201. Funding Information: This paper is partially supported by National Science Foundation, United States of America grant DMS-1763817 , U.S. Army Research Office grant W911NF-16-1-0404 and PSC-CUNY Award 3407-00 51, and is based upon work supported by the National Science Foundation, United States of America under Award No. DMS-1802201 . Publisher Copyright: © 2020 Elsevier B.V.

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 - http://www.scopus.com/inward/record.url?scp=85089079693&partnerID=8YFLogxK

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

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 -