List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\) (Q2198407)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\) |
scientific article |
Statements
List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\) (English)
0 references
10 September 2020
0 references
In this paper, a polynomial-time algorithm is given for the list 3-coloring problem restricted to the class of \(P_t\)-free graph with no induced 1-subdivision of \(K_{1,s}\). This complements several other partial results on a problem, which is well-known to be NP-hard in general.
0 references
coloring
0 references
forbidden induced subgraphs
0 references
dominating set
0 references
0 references
