Name
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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.disc.2020.112086 | Discrete Mathematics |
Keywords | DocType | Volume |
Coloring,Forbidden induced subgraphs,Dominating set | Journal | 343 |
Issue | ISSN | Citations |
11 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Chudnovsky | 1 | 390 | 46.13 |
| Sophie Theresa Spirkl | 2 | 8 | 7.36 |
| Mingxian Zhong | 3 | 7 | 4.25 |