The complexity of planar graph choosability
From MaRDI portal
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.
Recommendations
Cites work
- 3-list-coloring planar graphs of girth 5
- A not 3-choosable planar graph without 3-cycles
- Algorithmic complexity of list colorings
- Colorings and orientations of graphs
- Every planar graph is 5-choosable
- scientific article; zbMATH DE number 3735847 (Why is no real title available?)
- List colourings of planar graphs
- Multicriterial graph problems with MAXMIN criterion
- On the complexity of the disjoint paths problem
- Planar Formulae and Their Uses
- Some results on (a:b)-choosability
- Two-Processor Scheduling with Start-Times and Deadlines
Cited in
(46)- Some results on (a:b)-choosability
- On 3-choosable planar graphs of girth at least 4
- Planar graphs without cycles of length 4, 5, 8, or 9 are 3-choosable
- Color-critical graphs on a fixed surface
- Complexity of choosing subsets from color sets
- Path choosability of planar graphs
- Smaller planar triangle-free graphs that are not 3-list-colorable
- The 3-choosability of plane graphs of girth 4
- On structure of some plane graphs with application to choosability
- Coloring face-hypergraphs of graphs on surfaces
- Choosability of planar graphs
- Differences between the list-coloring and DP-coloring for planar graphs
- Planar graphs without pairwise adjacent 3-, 4-, 5-, and 6-cycle are 4-choosable
- The choice number versus the chromatic number for graphs embeddable on orientable surfaces
- On the subspace choosability in graphs
- DP-4-colorability of planar graphs without adjacent cycles of given length
- A note on 3-choosability of planar graphs
- On \(t\)-common list-colorings
- Optimal channel assignment with list-edge coloring
- Bordeaux 3-color conjecture and 3-choosability
- Phase transition of degeneracy in minor-closed families
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Threshold for path colorings of planar graphs
- Multiple list colouring of planar graphs
- scientific article; zbMATH DE number 890665 (Why is no real title available?)
- A sufficient condition for a planar graph to be 4-choosable
- Complexity of clique coloring and related problems
- List-coloring graphs without subdivisions and without immersions
- Dynamic list coloring of bipartite graphs
- 5-list coloring toroidal 6-regular triangulations in linear time
- Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable
- Group coloring and group connectivity with non-isomorphic groups of the same order
- Complexity of near-3-choosability problem
- On two problems of defective choosability of graphs
- Temporal reachability dominating sets: contagion in temporal graphs
- Exact and parameterized algorithms for choosability
- Planar graphs without cycles of specific lengths
- What is on his mind?
- The Alon-Tarsi number of planar graphs without some forbidden configurations
- 5-list coloring toroidal 6-regular triangulations in linear time
- Planar graphs without 4-cycles adjacent to triangles are 4-choosable
- Some recent progress and applications in graph minor theory
- Complexity of unique list colorability
- Locally planar graphs are 5-choosable
- On 3-choosability of planar graphs without certain cycles
- The minimum number of vertices for a triangle-free graph with \(\chi _l(G)=4\) is \(11\)
This page was built for publication: The complexity of planar graph choosability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1126188)
