The complexity of planar graph choosability (Q1126188): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Created claim: Wikidata QID (P12): Q56390733, #quickstatements; #temporary_batch_1712190744730
Property / Wikidata QID
 
Property / Wikidata QID: Q56390733 / rank
 
Normal rank

Revision as of 01:51, 4 April 2024

scientific article
Language Label Description Also known as
English
The complexity of planar graph choosability
scientific article

    Statements

    The complexity of planar graph choosability (English)
    0 references
    0 references
    18 June 1997
    0 references
    Margit Voigt gave examples of a planar graph which is not 4-choosable and a planar triangle-free graph which is not 3-choosable. The present author presents simpler examples. He also proves that the corresponding decision problems for planar graphs are NP-hard.
    0 references
    choosability
    0 references
    planar graph
    0 references
    decision problems
    0 references
    NP-hard
    0 references

    Identifiers