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)
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (35)
The choice number versus the chromatic number for graphs embeddable on orientable surfaces ⋮ On the subspace choosability in graphs ⋮ A note on 3-choosability of planar graphs ⋮ Multiple list colouring of planar graphs ⋮ Color-critical graphs on a fixed surface ⋮ On \(t\)-common list-colorings ⋮ Some recent progress and applications in graph minor theory ⋮ Dynamic list coloring of bipartite graphs ⋮ Optimal channel assignment with list-edge coloring ⋮ 5-list coloring toroidal 6-regular triangulations in linear time ⋮ Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable ⋮ Phase transition of degeneracy in minor-closed families ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Complexity of unique list colorability ⋮ Locally planar graphs are 5-choosable ⋮ A sufficient condition for a planar graph to be 4-choosable ⋮ On 3-choosability of planar graphs without certain cycles ⋮ Planar graphs without cycles of specific lengths ⋮ Bordeaux 3-color conjecture and 3-choosability ⋮ Complexity of clique coloring and related problems ⋮ Smaller planar triangle-free graphs that are not 3-list-colorable ⋮ What is on his mind? ⋮ The 3-choosability of plane graphs of girth 4 ⋮ Differences between the list-coloring and DP-coloring for planar graphs ⋮ The minimum number of vertices for a triangle-free graph with \(\chi _l(G)=4\) is \(11\) ⋮ Planar graphs without 4-cycles adjacent to triangles are 4-choosable ⋮ DP-4-colorability of planar graphs without adjacent cycles of given length ⋮ Some results on \((a:b)\)-choosability ⋮ On 3-choosable planar graphs of girth at least 4 ⋮ Planar graphs without pairwise adjacent 3-, 4-, 5-, and 6-cycle are 4-choosable ⋮ Planar graphs without cycles of length 4, 5, 8, or 9 are 3-choosable ⋮ Complexity of choosing subsets from color sets ⋮ On structure of some plane graphs with application to choosability ⋮ Coloring face-hypergraphs of graphs on surfaces ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- 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
This page was built for publication: The complexity of planar graph choosability
