List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\) (Q2198407)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: List 3-coloring P_t-free graphs with no induced 1-subdivision of K₁ , s |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.8082807064056396
0 references
0.7910476326942444
0 references
0.7909190058708191
0 references
0.7896685004234314
0 references
0.7835269570350647
0 references
