Every planar graph is 5-choosable
From MaRDI portal
Publication:1333334
DOI10.1006/jctb.1994.1062zbMath0805.05023OpenAlexW2089023036WikidataQ56390727 ScholiaQ56390727MaRDI QIDQ1333334
Publication date: 26 January 1995
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jctb.1994.1062
Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)
Related Items
Algorithmic complexity of list colorings ⋮ Five-list-coloring graphs on surfaces. II: A linear bound for critical graphs in a disk. ⋮ DP-3-coloring of some planar graphs ⋮ The edge-face choosability of plane graphs ⋮ Graph polynomials and paintability of plane graphs ⋮ The Alon-Tarsi number of planar graphs ⋮ The 4-choosability of toroidal graphs without intersecting triangles ⋮ A note on not-4-list colorable planar graphs ⋮ A \((3,1)^\ast\)-choosable theorem on planar graphs ⋮ A not 3-choosable planar graph without 3-cycles ⋮ The number of \(k\)-colorings of a graph on a fixed surface ⋮ 5-list-coloring planar graphs with distant precolored vertices ⋮ Multiple list colouring of planar graphs ⋮ Extension from precoloured sets of edges ⋮ A new sufficient condition for a toroidal graph to be 4-choosable ⋮ Color-critical graphs on a fixed surface ⋮ Coloring planar homothets and three-dimensional hypergraphs ⋮ Homomorphism bounds for oriented planar graphs of given minimum girth ⋮ Many 3-colorings of triangle-free planar graphs ⋮ Some recent progress and applications in graph minor theory ⋮ A small non-\(\mathbb Z_4\)-colorable planar graph ⋮ The complexity of planar graph choosability ⋮ List homomorphisms to reflexive graphs ⋮ A sufficient condition for planar graphs to be (3,1)-choosable ⋮ Exponentially many 5-list-colorings of planar graphs ⋮ Five-list-coloring graphs on surfaces. III: One list of size one and one list of size two ⋮ Dynamic coloring parameters for graphs with given genus ⋮ Choosability with union separation ⋮ Choosability in signed planar graphs ⋮ On the complexity of some colorful problems parameterized by treewidth ⋮ The chromatic number of a graph of girth 5 on a fixed surface ⋮ A short list color proof of Grötzsch's theorem ⋮ Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable ⋮ On facial unique-maximum (edge-)coloring ⋮ Planar graphs without 4- and 5-cycles are acyclically 4-choosable ⋮ From the plane to higher surfaces ⋮ On 3-choosability of plane graphs without 6-, 7- and 9-cycles ⋮ Some structural properties of planar graphs and their applications to 3-choosability ⋮ Acyclic 6-choosability of planar graphs without adjacent short cycles ⋮ Another proof of the 5-choosability of \(K_5\)-minor-free graphs ⋮ Maximum 4-degenerate subgraph of a planar graph ⋮ The 4-choosability of planar graphs and cycle adjacency ⋮ 5-choosability of graphs with crossings far apart ⋮ An introduction to the discharging method via graph coloring ⋮ Every planar graph without pairwise adjacent 3-, 4-, and 5-cycle is DP-4-colorable ⋮ List coloring of planar graphs with forbidden cycles ⋮ Degree choosable signed graphs ⋮ On-line list coloring of matroids ⋮ Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8 ⋮ On \((k, k n - k^2 - 2 k - 1)\)-choosability of \(n\)-vertex graphs ⋮ Planar graphs without chordal 6-cycles are 4-choosable ⋮ A sufficient condition for DP-4-colorability ⋮ Splitting a planar graph of girth 5 into two forests with trees of small diameter ⋮ Every plane graph is facially-non-repetitively \(C\)-choosable ⋮ Defective 3-paintability of planar graphs ⋮ Locally planar graphs are 5-choosable ⋮ 2-list-coloring planar graphs without monochromatic triangles ⋮ A sufficient condition for a planar graph to be 4-choosable ⋮ On the \((3, 1)\)-choosability of planar graphs without adjacent cycles of length \(5, 6, 7\) ⋮ DP-3-coloring of planar graphs without 4, 9-cycles and cycles of two lengths from \(\{6,7,8\}\) ⋮ Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable ⋮ Sufficient conditions on planar graphs to have a relaxed DP-3-coloring ⋮ On 3-choosability of planar graphs without certain cycles ⋮ List precoloring extension in planar graphs ⋮ Planar graphs without cycles of specific lengths ⋮ Choosability with union separation of triangle-free planar graphs ⋮ Acyclic improper choosability of subcubic graphs ⋮ Planar graphs are 1-relaxed, 4-choosable ⋮ On group choosability of graphs. II ⋮ A note on the acyclic 3-choosability of some planar graphs ⋮ Acyclic 3-choosability of sparse graphs with girth at least 7 ⋮ What is on his mind? ⋮ Acyclic 4-choosability of planar graphs with neither 4-cycles nor triangular 6-cycles ⋮ Contractibility and the Hadwiger conjecture ⋮ Acyclic 4-choosability of planar graphs without adjacent short cycles ⋮ A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model ⋮ Five-coloring graphs on the Klein bottle ⋮ The 3-choosability of plane graphs of girth 4 ⋮ A note on the DP-chromatic number of complete bipartite graphs ⋮ Every planar graph without cycles of lengths 4 to 12 is acyclically 3-choosable ⋮ On choosability with separation of planar graphs without adjacent short cycles ⋮ The chromatic polynomial and list colorings ⋮ Planar graphs without 4-cycles adjacent to triangles are 4-choosable ⋮ On the choice number of complete multipartite graphs with part size four ⋮ You can't paint yourself into a corner ⋮ On 3-choosable planar graphs of girth at least 4 ⋮ Decomposing a planar graph of girth 5 into an independent set and a forest ⋮ List-coloring graphs without \(K_{4,k}\)-minors ⋮ Extending graph colorings ⋮ The list chromatic numbers of some planar graphs ⋮ Planar graphs without 3-, 7-, and 8-cycles are 3-choosable ⋮ Acyclic 5-choosability of planar graphs with neither 4-cycles nor chordal 6-cycles ⋮ Planar graphs without cycles of length 4, 5, 8, or 9 are 3-choosable ⋮ Choosability, edge choosability and total choosability of outerplane graphs ⋮ Choosability of \(K_5\)-minor-free graphs ⋮ On structure of some plane graphs with application to choosability ⋮ Decomposing a planar graph into an independent set and a 3-degenerate graph ⋮ Coloring face-hypergraphs of graphs on surfaces ⋮ The 4-choosability of plane graphs without 4-cycles ⋮ Group coloring is \(\Pi_2^{\text{P}}\)-complete ⋮ Improved lower bound for the list chromatic number of graphs with no Kt minor ⋮ Improper Choosability and Property B ⋮ Kempe equivalence of 4‐critical planar graphs ⋮ Weak degeneracy of graphs ⋮ Flexibility of triangle‐free planar graphs ⋮ 3‐Degenerate induced subgraph of a planar graph ⋮ Decomposing planar graphs into graphs with degree restrictions ⋮ 5-list coloring toroidal 6-regular triangulations in linear time ⋮ Variable degeneracy on toroidal graphs ⋮ The Alon–Tarsi number of planar graphs revisited ⋮ The Alon-Tarsi number of two kinds of planar graphs ⋮ List 4-colouring of planar graphs ⋮ On the Alon-Tarsi number of semi-strong product of graphs ⋮ Decomposing a triangle-free planar graph into a forest and a subcubic forest ⋮ Schnyder woods and Alon-Tarsi number of planar graphs ⋮ A strengthening and an efficient implementation of Alon-Tarsi list coloring method ⋮ Acyclic 5-choosability of planar graphs without 4-cycles ⋮ Acyclic 5-choosability of planar graphs without 4-cycles ⋮ Islands in Graphs on Surfaces ⋮ Amenable colorings ⋮ Some Conjectures and Questions in Chromatic Topological Graph Theory ⋮ Unnamed Item ⋮ The choice number versus the chromatic number for graphs embeddable on orientable surfaces ⋮ Graph polynomials and group coloring of graphs ⋮ Improved bounds for colouring circle graphs ⋮ A sufficient condition for planar graphs to be acyclically 5-choosable ⋮ The asymptotic behavior of the correspondence chromatic number ⋮ Facial list colourings of plane graphs ⋮ Acyclic list 7‐coloring of planar graphs ⋮ An extension of Thomassen's result on choosability ⋮ Acyclic 5-choosability of planar graphs without adjacent short cycles ⋮ Graph theory -- a survey on the occasion of the Abel Prize for László Lovász ⋮ Planar graphs without normally adjacent short cycles ⋮ A sufficient condition for a planar graph to be 3-choosable ⋮ A note on 3-choosability of planar graphs ⋮ List Colorings of K5-Minor-Free Graphs With Special List Assignments ⋮ Choosability of P 5-Free Graphs ⋮ Hyperbolic families and coloring graphs on surfaces ⋮ Planar graphs without intersecting 5-cycles are 4-choosable ⋮ Choosability with union separation of planar graphs without cycles of length 4 ⋮ Every planar graph is 1-defective \((9,2)\)-paintable ⋮ Reconfiguring 10-colourings of planar graphs ⋮ DP-colorings of graphs with high chromatic number ⋮ On \(t\)-common list-colorings ⋮ Facially-constrained colorings of plane graphs: a survey ⋮ Facial unique-maximum edge and total coloring of plane graphs ⋮ Dynamic list coloring of 1-planar graphs ⋮ List-coloring -- parameterizing from triviality ⋮ \((4,2)\)-choosability of planar graphs with forbidden structures ⋮ Strengthening \((a,b)\)-choosability results to \((a,b)\)-paintability ⋮ Unnamed Item ⋮ Colouring planar graphs with bounded monochromatic components ⋮ Vertex colourings of multigraphs with forbiddances on edges ⋮ Planar graphs without 7-cycles and butterflies are DP-4-colorable ⋮ A generalization of some results on list coloring and DP-coloring ⋮ 4-choosability of planar graphs with 4-cycles far apart via the Combinatorial Nullstellensatz ⋮ On-line DP-coloring of graphs ⋮ Flow extensions and group connectivity with applications ⋮ Phase transition of degeneracy in minor-closed families ⋮ 不含带弦6-圈和项链图的平面图是DP-4-可染的 ⋮ Local 7-coloring for planar subgraphs of unit disk graphs ⋮ The Alon-Tarsi number of a planar graph minus a matching ⋮ A note on 3-choosability of plane graphs under distance restrictions ⋮ On spanning trees without vertices of degree 2 in plane triangulations ⋮ 3-choosability of planar graphs with \((\leqslant 4)\)-cycles far apart ⋮ On \(( 2 , r )\)-choosability of planar graphs without short cycles ⋮ Every toroidal graph is acyclically 8-choosable ⋮ On list-coloring outerplanar graphs ⋮ Dirac's map-color theorem for choosability ⋮ Dynamic coloring and list dynamic coloring of planar graphs ⋮ On the chromatic polynomial and counting DP-colorings of graphs ⋮ Concepts of signed graph coloring ⋮ Flexibility of planar graphs -- sharpening the tools to get lists of size four ⋮ New approach to nonrepetitive sequences ⋮ Circular consecutive choosability of k-choosable graphs ⋮ Acyclic 4‐Choosability of Planar Graphs with No 4‐ and 5‐Cycles ⋮ Additive non-approximability of chromatic number in proper minor-closed classes ⋮ Five-list-coloring graphs on surfaces. I. Two lists of size two in planar graphs ⋮ Bordeaux 3-color conjecture and 3-choosability ⋮ Choosability of toroidal graphs without short cycles ⋮ Improper coloring of unit disk graphs ⋮ Answers to two questions on the DP color function ⋮ Differences between the list-coloring and DP-coloring for planar graphs ⋮ A refinement of choosability of graphs ⋮ Choosability with separation of planar graphs without prescribed cycles ⋮ A Thomassen-type method for planar graph recoloring ⋮ List coloring and diagonal coloring for plane graphs of diameter two ⋮ On Choosability with Separation of Planar Graphs with Forbidden Cycles ⋮ Exponentially many \(\mathbb{Z}_5\)-colorings in simple planar graphs ⋮ Acyclic 6-choosability of planar graphs without 5-cycles and adjacent 4-cycles ⋮ List Colorings with Distinct List Sizes, the Case of Complete Bipartite Graphs ⋮ DP-4-colorability of planar graphs without adjacent cycles of given length ⋮ Group connectivity and group coloring: small groups versus large groups ⋮ An analogue of DP-coloring for variable degeneracy and its applications ⋮ Hadwiger’s Conjecture ⋮ Facial unique-maximum colorings of plane graphs with restriction on big vertices ⋮ Coloring of Plane Graphs with Unique Maximal Colors on Faces ⋮ Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable ⋮ Circular choosability ⋮ Planar graphs without 4-cycles are acyclically 6-choosable ⋮ Adapted list coloring of planar graphs ⋮ The Alon-Tarsi number of \(K_5\)-minor-free graphs ⋮ DP-\(4\)-colorability of planar graphs without intersecting \(5\)-cycles ⋮ Note on 3-choosability of planar graphs with maximum degree 4 ⋮ Planar graphs without pairwise adjacent 3-, 4-, 5-, and 6-cycle are 4-choosable ⋮ Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs ⋮ Acyclic choosability of planar graphs: a Steinberg like approach ⋮ Alon-Tarsi number and modulo Alon-Tarsi number of signed graphs ⋮ Distributed coloring in sparse graphs with fewer colors ⋮ IC-Planar Graphs Are 6-Choosable ⋮ DP-coloring on planar graphs without given adjacent short cycles ⋮ Additive non-approximability of chromatic number in proper minor-closed classes ⋮ Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles ⋮ A map colour theorem for the union of graphs ⋮ Extending partial 5-colorings and 6-colorings in planar graphs ⋮ Locally planar graphs are 5-paintable ⋮ On choosability with separation of planar graphs with lists of different sizes ⋮ Acyclic improper choosability of graphs ⋮ The polynomial method for list-colouring extendability of outerplanar graphs ⋮ Toroidal graphs containing neither nor 6‐cycles are 4‐choosable ⋮ On sufficient conditions for planar graphs to be 5-flexible ⋮ On \((3, r)\)-choosability of some planar graphs
