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

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

zbMATH Keywords

choosability

0 references

planar graph

0 references

decision problems

0 references

NP-hard

0 references

reviewed by

Carsten Thomassen

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Colorings and orientations of graphs

0 references

Q3922703

0 references

Two-Processor Scheduling with Start-Times and Deadlines

0 references

Some results on \((a:b)\)-choosability

0 references

Algorithmic complexity of list colorings

0 references

Planar Formulae and Their Uses

0 references

On the complexity of the disjoint paths problem

0 references

Every planar graph is 5-choosable

0 references

3-list-coloring planar graphs of girth 5

0 references

Q3115277

0 references

List colourings of planar graphs

0 references

A not 3-choosable planar graph without 3-cycles

0 references

Identifiers

zbMATH Open document ID

0865.05066

0 references

DOI

10.1016/0012-365X(95)00104-5

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1126188

@@ Property / cites work @@
+Colorings and orientations of graphs
@@ Property / cites work: Colorings and orientations of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3922703
@@ Property / cites work: Q3922703 / rank @@
+Normal rank
@@ Property / cites work @@
+Two-Processor Scheduling with Start-Times and Deadlines
+Normal rank
@@ Property / cites work @@
+Some results on \((a:b)\)-choosability
@@ Property / cites work: Some results on \((a:b)\)-choosability / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithmic complexity of list colorings
@@ Property / cites work: Algorithmic complexity of list colorings / rank @@
+Normal rank
@@ Property / cites work @@
+Planar Formulae and Their Uses
@@ Property / cites work: Planar Formulae and Their Uses / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of the disjoint paths problem
@@ Property / cites work: On the complexity of the disjoint paths problem / rank @@
+Normal rank
@@ Property / cites work @@
+Every planar graph is 5-choosable
@@ Property / cites work: Every planar graph is 5-choosable / rank @@
+Normal rank
@@ Property / cites work @@
+-list-coloring planar graphs of girth 5
@@ Property / cites work: 3-list-coloring planar graphs of girth 5 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3115277
@@ Property / cites work: Q3115277 / rank @@
+Normal rank
@@ Property / cites work @@
+List colourings of planar graphs
@@ Property / cites work: List colourings of planar graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A not 3-choosable planar graph without 3-cycles
@@ Property / cites work: A not 3-choosable planar graph without 3-cycles / rank @@
+Normal rank