The complexity of planar graph choosability
From MaRDI portal
Publication:1126188
DOI10.1016/0012-365X(95)00104-5zbMath0865.05066WikidataQ56390733 ScholiaQ56390733MaRDI QIDQ1126188
Publication date: 18 June 1997
Published in: Discrete Mathematics (Search for Journal in Brave)
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, Multiple list colouring of planar graphs, A sufficient condition for a planar graph to be 4-choosable, Complexity of clique coloring and related problems, Dynamic list coloring of bipartite graphs, Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable, Planar graphs without cycles of specific lengths, What is on his mind?, 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\), 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, 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, Differences between the list-coloring and DP-coloring for planar 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, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
Cites Work
- List colourings of planar graphs
- Some results on \((a:b)\)-choosability
- Colorings and orientations of graphs
- Algorithmic complexity of list colorings
- Every planar graph is 5-choosable
- 3-list-coloring planar graphs of girth 5
- A not 3-choosable planar graph without 3-cycles
- On the complexity of the disjoint paths problem
- Planar Formulae and Their Uses
- Two-Processor Scheduling with Start-Times and Deadlines
- Unnamed Item
- Unnamed Item
