Every planar map is four colorable

DOI10.1090/S0002-9904-1976-14122-5zbMath0331.05106WikidataQ56390610 ScholiaQ56390610MaRDI QIDQ4097312

Kenneth I. Appel

Publication date: 1976

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (only showing first 100 items - show all)

Rainbow subgraphs in edge-colored planar and outerplanar graphs ⋮ On zonal and inner zonal labelings of plane graphs of maximum degree 3 ⋮ Clique minors in graphs with a forbidden subgraph ⋮ Square Coloring Planar Graphs with Automatic Discharging ⋮ Transversals and colorings of simplicial spheres ⋮ A Five-Color Theorem for Graphs on Surfaces ⋮ Bicircular matroids are 3-colorable ⋮ A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings ⋮ Strict neighbor-distinguishing total index of graphs ⋮ Extending precolorings of subgraphs of locally planar graphs ⋮ Homomorphism bounded classes of graphs ⋮ Asymptotic dimension of planes and planar graphs ⋮ The cost of perfection for matchings in graphs ⋮ Book embedding of locally planar graphs on orientable surfaces ⋮ Topological Graph Theory: A Personal Account ⋮ From realizability to induction via dependent intersection ⋮ A sufficient condition for a planar graph to be \((\mathcal{F},\mathcal{F}_2)\)-partitionable ⋮ Vector colorability ⋮ Colorings and girth of oriented planar graphs ⋮ A categorical setting for the 4-colour theorem ⋮ Cyclic 4-Colorings of Graphs on Surfaces ⋮ Supereulerian graphs and excluded induced minors ⋮ Complete Minors in Graphs Without Sparse Cuts ⋮ Zig-zag facial total-coloring of plane graphs ⋮ Hadwiger's conjecture for circular colorings of edge-weighted graphs ⋮ Computing the Ramsey number \(R(4,3,3)\) using abstraction and symmetry breaking ⋮ An implicit numerical scheme for the simulation of internal viscous flow on unstructured grids ⋮ Colorings of plane graphs without long monochromatic facial paths ⋮ Even-cycle decompositions of graphs with no odd-\(K_4\)-minor ⋮ Facially-constrained colorings of plane graphs: a survey ⋮ Facial unique-maximum edge and total coloring of plane graphs ⋮ On intersection representations of co-planar graphs ⋮ Entire coloring of 2-connected plane graphs ⋮ An annotated bibliography on 1-planarity ⋮ Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ Upper bounds on adjacent vertex distinguishing total chromatic number of graphs ⋮ Strong chromatic index of \(K_4\)-minor free graphs ⋮ Coloring Eulerian triangulations of the Klein bottle ⋮ Distance constraints in graph color extensions ⋮ Unnamed Item ⋮ Edge-coloring of plane multigraphs with many colors on facial cycles ⋮ Computer-aided proof of Erdős discrepancy properties ⋮ Ugly mathematics: why do mathematicians dislike computer-assisted proofs? ⋮ Domination parameters of a graph and its complement ⋮ Planar graphs with \(\Delta =9\) are neighbor-distinguishing totally 12-colorable ⋮ Facial entire colouring of plane graphs ⋮ Improved square coloring of planar graphs ⋮ On the vertex-arboricity of planar graphs ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Local neighbor-distinguishing index of graphs ⋮ A note on half-planar geometries ⋮ On backbone coloring of graphs ⋮ Maximal strip recovery problem with gaps: hardness and approximation algorithms ⋮ How reliable is a computer-based proof? ⋮ Facial parity edge colouring of plane pseudographs ⋮ On Neighbourly Triangulations ⋮ A survey of graph coloring - its types, methods and applications ⋮ Maximum face-constrained coloring of plane graphs ⋮ A survey on the cyclic coloring and its relaxations ⋮ The adjacent vertex distinguishing total coloring of planar graphs ⋮ Steinberg-like theorems for backbone colouring ⋮ Entire colouring of plane graphs ⋮ Bounds on the connected domination number of a graph ⋮ On coloring box graphs ⋮ List 2-facial 5-colorability of plane graphs with girth at least 12 ⋮ Cyclic colorings of plane graphs with independent faces ⋮ Guthrie's problem: new equivalences and rapid reductions ⋮ Labelling planar graphs without 4-cycles with a condition on distance two ⋮ Chromatic numbers of quadrangulations on closed surfaces ⋮ Conjecture de Hadwiger: \(k=6\). II: Réductions de sommets de degré 6 dans les graphes 6-chromatiques contraction-critiques. (Hardwiger's conjecture: \(k=6\). II: Reductions of 6-vertices in 6-chromatic contraction-critical graphs) ⋮ Induced 2-degenerate subgraphs of triangle-free planar graphs ⋮ WORM colorings of planar graphs ⋮ Entire coloring of graphs embedded in a surface of nonnegative characteristic ⋮ Uncertain vertex coloring problem ⋮ Adjacent vertex distinguishing total colorings of outerplanar graphs ⋮ A bound on the chromatic number of the square of a planar graph ⋮ Rotation sequences and edge-colouring of binary tree pairs ⋮ Unnamed Item ⋮ On the chromatic number of binary matroids ⋮ The thickness and chromatic number of \(r\)-inflated graphs ⋮ Colouring Random Empire Trees ⋮ Coloring plane graphs with independent crossings ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Facial achromatic number of triangulations on the sphere ⋮ Large Independent Sets in Subquartic Planar Graphs ⋮ Large Independent Sets in Triangle-Free Planar Graphs ⋮ Bounds and fixed-parameter algorithms for weighted improper coloring ⋮ An algebraic approach to the planar coloring problem ⋮ The edge version of Hadwiger's conjecture ⋮ The edge-face coloring of graphs embedded in a surface of characteristic zero ⋮ The existence of uniform hypergraphs for which the interpolation property of complete coloring fails ⋮ A complete classification of tractability in Allen's algebra relative to subsets of basic relations ⋮ Unnamed Item ⋮ Ising spins on thin graphs ⋮ deBruijn-like sequences and the irregular chromatic number of paths and cycles ⋮ Chromatic numbers of simplicial manifolds ⋮ Antisymmetric flows and strong colourings of oriented graphs ⋮ Some Conjectures and Questions in Chromatic Topological Graph Theory ⋮ Edge-partition and star chromatic index ⋮ The Zambelli Attractors of Coupled, Nonlinear Macrodynamics and Knot Theory

Cites Work

• The existence of unavoidable sets of geographically good configurations
• A systematic approach to the determination of reducible configurations in the four-color conjecture
• Unnamed Item
• Unnamed Item

This page was built for publication: Every planar map is four colorable