Every planar map is four colorable. I: Discharging
From MaRDI portal
Publication:1250223
zbMath0387.05009MaRDI QIDQ1250223
Kenneth I. Appel, Wolfgang Haken
Publication date: 1977
Published in: Illinois Journal of Mathematics (Search for Journal in Brave)
Related Items
Every planar graph without cycles of length 4 or 9 is \((1, 1, 0)\)-colorable, Improved lower bound for the list chromatic number of graphs with no Kt minor, On computer-assisted proving the existence of periodic and bounded orbits, Efficient Vertex- and Edge-Coloring of Outerplanar Graphs, Light structures in infinite planar graphs without the strong isoperimetric property, Harmonious coloring: parameterized algorithms and upper bounds, Unnamed Item, Six-Critical Graphs on the Klein Bottle, Harmonious Coloring: Parameterized Algorithms and Upper Bounds, The challenge of computer mathematics, Unnamed Item, Conflict-Free Coloring of Graphs, Hyperbolic families and coloring graphs on surfaces, Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs, 2-Distance Coloring of Sparse Graphs, On the number of vertices of positively curved planar graphs, On star 5-colorings of sparse graphs, On \(t\)-common list-colorings, Facially-constrained colorings of plane graphs: a survey, On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs, Responses to ``Theoretical Mathematics: Toward\\ a cultural synthesis of mathematics and\\ theoretical physics, by A. Jaffe and F. Quinn, Triangle-free graphs of tree-width \(t\) are \(\lceil (t+3)/2 \rceil\)-colorable, Properties of Large 2-Crossing-Critical Graphs, Cyclic coloring of plane graphs with maximum face size 16 and 17, The adjacent vertex distinguishing total chromatic numbers of planar graphs with \(\Delta=10\), \(\mathsf{NIC}\)-planar graphs, A Uniform Family of Tissue P Systems with Protein on Cells Solving 3-Coloring in Linear Time, Formalizing Size-Optimal Sorting Networks: Extracting a Certified Proof Checker, 3-Coloring Triangle-Free Planar Graphs with a Precolored 9-Cycle, Planar graphs with $\Delta\geq 8$ are ($\Delta+1$)-edge-choosable, Facial \([r,s,t\)-colorings of plane graphs], Hadwiger's Conjecture for Graphs with Forbidden Holes, Inductive graph invariants and approximation algorithms, On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree, 4-choosability of planar graphs with 4-cycles far apart via the Combinatorial Nullstellensatz, Unnamed Item, Unnamed Item, 3-choosability of planar graphs with \((\leqslant 4)\)-cycles far apart, Defective 2-colorings of sparse graphs, Improper colorability of planar graphs without prescribed short cycles, Towards nonconservative conditions for equilibrium stability. Applications to switching systems with control delay, Nowhere–zero bases for the nullspace of the incidence matrices of graphs, Breaking the degeneracy barrier for coloring graphs with no \(K_t\) minor, Properties of 8-contraction-critical graphs with no \(K_7\) minor, Hadwiger's conjecture for quasi-line graphs, (1,k)-Coloring of Graphs with Girth at Least Five on a Surface, Computation in Causal Graphs, Planar graphs with cycles of length neither 4 nor 6 are \((2,0,0)\)-colorable, Dynamic coloring and list dynamic coloring of planar graphs, \((1,0,0)\)-colorability of planar graphs without cycles of length 4, 5 or 9, Planar graphs with cycles of length neither 4 nor 7 are \((3,0,0)\)-colorable, A note on face coloring entire weightings of plane graphs, Randomized Competitive Analysis for Two-Server Problems, Problems on pairs of trees and the four colour problem of planar graphs, The genus of Petersen powers, An approximate version of Hadwiger's conjecture for claw-free graphs, Spanning cycles in regular matroids without \(M^{*}(K_{5})\) minors, Proof of Conway’s lost cosmological theorem, Fractional coloring and the odd Hadwiger's conjecture, Grünbaum colorings of toroidal triangulations, Conditional colorings of graphs, Hadwiger number and chromatic number for near regular degree sequences, Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k, An introduction to univalent foundations for mathematicians, Improper coloring of unit disk graphs, Third Case of the Cyclic Coloring Conjecture, An unavoidable set of $D$-reducible configurations, Cognitive Science and the Connection Between Physics and Mathematics, The k-conversion number of regular graphs, Coloring \(d\)-embeddable \(k\)-uniform hypergraphs, On the odd-minor variant of Hadwiger's conjecture, Theory of Quantum Computation and Philosophy of Mathematics. Part II, Hadwiger’s Conjecture and Squares of Chordal Graphs, Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths, Large Induced Forests in Graphs, Hadwiger’s Conjecture, Delta diagrams, CATEGORY-BASED CO-GENERATION OF SEMINAL CONCEPTS AND RESULTS IN ALGEBRA AND NUMBER THEORY: CONTAINMENT-DIVISION AND GOLDBACH RINGS, On Tutte’s chromatic invariant, On BMRN*-colouring of planar digraphs, Toward Computer-Assisted Discovery and Automated Proofs of Cutting Plane Theorems, Subcubic triangle-free graphs have fractional chromatic number at most 14/5, Kernelization: New Upper and Lower Bound Techniques, Unnamed Item, Planar graphs with girth at least 5 are \((3, 4)\)-colorable, $$\textit{\textbf{k}}$$-Planar Graphs, Tutte Polynomials and Link Polynomials, Computers as a Source of A Posteriori Knowledge in Mathematics, Kempe-locking configurations, COMPUTER TOOLS FOR SOLVING MATHEMATICAL PROBLEMS: A REVIEW, Unnamed Item, On vertex rankings of graphs and its relatives, Perspectives on American mathematics, A Linear–time Tissue P System Based Solution for the 3–coloring Problem, The Significance of Relativistic Computation for the Philosophy of Mathematics, From light edges to strong edge-colouring of 1-planar graphs, The dimension of a graph, Solving the Watchman Route Problem with Heuristic Search, Limits of Near-Coloring of Sparse Graphs, Sums of Palindromes: an Approach via Automata, Three-edge-colouring doublecross cubic graphs, A proof via finite elements for Schiffer's conjecture on a regular pentagon, Generators and normal forms of Richard Thompson's group \(F\) and the four-color theorem, Outer 1-planar graphs, Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle., On a Heawood-type problem for maps with tangencies, I,F-partitions of sparse graphs, Fullerene graphs have exponentially many perfect matchings, Heawood inequalities, Planar graphs have independence ratio at least 3/13, On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P, Map coloring and the vector cross product, Third case of the cyclic coloring conjecture, Coloring immersion-free graphs, On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture, A fast parallel coloring of planar graphs with five colors, Optimal-depth sorting networks, 5-list-coloring planar graphs with distant precolored vertices, Hadwiger's conjecture (ḵ\(=6):\) Neighbour configurations of 6-vertices in contraction-critical graphs, Solution of the propeller conjecture in \(\mathbb R^3\), Some recent progress and applications in graph minor theory, On the maximum number of edges in quasi-planar graphs, A relaxed Hadwiger's conjecture for list colorings, On \(r\)-hued coloring of \(K_4\)-minor free graphs, Graphs with maximum degree \(\varDelta\geq 17\) and maximum average degree less than 3 are list 2-distance \((\varDelta +2)\)-colorable, Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable, Challenges to the assessment of time-to-proof of mathematical conjectures, Interval matroids and graphs, On 1-improper 2-coloring of sparse graphs, On word-representability of polyomino triangulations, Toward a language theoretic proof of the four color theorem, \((k,1)\)-coloring of sparse graphs, \((k,j)\)-coloring of sparse graphs, Planar graphs without cycles of length 4 or 5 are \((2, 0, 0)\)-colorable, Planar graphs without 5-cycles and intersecting triangles are \((1, 1, 0)\)-colorable, On dynamic coloring for planar graphs and graphs of higher genus, On a generalization of ``eight blocks to madness puzzle, Computer-assisted proof of performance ratios for the differencing method, Coloring algorithms for \(K_ 5\)-minor free graphs, Kempe classes and the Hadwiger conjecture, Euler index in uncertain graph, Coloring certain proximity graphs, Randomly colouring graphs (a combinatorial view), Is the five-flow conjecture almost false?, Strong chromatic index of planar graphs with large girth, A note on vertex colorings of plane graphs, Automated theorem provers: a practical tool for the working mathematician?, Zero-sum flows of the linear lattice., On the tractability of some natural packing, covering and partitioning problems, Finding the exact bound of the maximum degrees of class two graphs embeddable in a surface of characteristic \(\epsilon \in \{-1, -2, -3\}\), Can strategizing in round-robin subtournaments be avoided?, Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence, Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1, Planar graphs with girth at least 5 are \((3, 5)\)-colorable, Edge-colouring seven-regular planar graphs, Edge-colouring eight-regular planar graphs, Tree-like distance colouring for planar graphs of sufficient girth, Guthrie's problem: new equivalences and rapid reductions, Hadwiger's conjecture for inflations of 3-chromatic graphs, An introduction to mechanized reasoning, Guarding polyhedral terrains, Edge guarding polyhedral terrains, An introduction to the discharging method via graph coloring, Some remarks on the odd Hadwiger's conjecture, Thickness and colorability of geometric graphs, The adjacent vertex distinguishing total coloring of planar graphs without adjacent 4-cycles, A uniform family of tissue P systems with cell division solving 3-COL in a linear time, The \(a\)-graph coloring problem, Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8, Binary pattern tile set synthesis is NP-hard, Acyclically 3-colorable planar graphs, Facial colorings using Hall's theorem, Rotation sequences and edge-colouring of binary tree pairs, A simple algorithm for 4-coloring 3-colorable planar graphs, Five-coloring graphs on the Klein bottle, Graph theory (algorithmic, algebraic, and metric problems), Extending planar graph algorithms to \(K_{3,3}\)-free graphs, Planar graphs without 4-cycles and close triangles are \((2,0,0)\)-colorable, Edge-choosability of planar graphs without adjacent triangles or without 7-cycles, List coloring the square of sparse graphs with large degree, Nowhere-zero 4-flow in almost Petersen-minor free graphs, A bound on the chromatic number of an almost planar graph, Linear connectivity forces large complete bipartite minors, Note on coloring graphs without odd-\(K_k\)-minors, List-coloring graphs without \(K_{4,k}\)-minors, The Voronoi diagram of three lines, Clique minors in claw-free graphs, Graph coloring: a novel heuristic based on trailing path-properties, perspective and applications in structured networks, Cliques, minors and apex graphs, Thickness-two graphs. II: More new nine-critical graphs, independence ratio, cloned planar graphs, and singly and doubly outerplanar graphs, Solving the 3-COL problem by using tissue P systems without environment and proteins on cells, Planar graphs without adjacent cycles of length at most seven are 3-colorable, Ensemble convexes dans les graphes. I: Théoremes de Helly et de Radon pour graphes et surfaces, Efficient bounds for the stable set, vertex cover and set packing problems, On linear-time algorithms for five-coloring planar graphs, Shortest coverings of graphs with cycles, Planar graph coloring is not self-reducible, assuming P\(\neq NP\), The four color proof suffices, 5-connected 3-polytopes are refinements of octahedra, Regular independent sets, 1-planar graphs are odd 13-colorable, Wheels in planar graphs and Hajós graphs, An (F1,F4)‐partition of graphs with low genus and girth at least 6, Circular coloring and fractional coloring in planar graphs, Coloring count cones of planar graphs, 4‐Separations in Hajós graphs, Path partition of planar graphs with girth at least six, A uniform family of tissue P systems with protein on cells solving 3-coloring in linear time, Optimizing concurrency under Scheduling by Edge Reversal, Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width, Enumerative combinatorics. Abstracts from the workshop held December 11--17, 2022, Weakening total coloring conjecture and Hadwiger's conjecture on total graphs, Colouring perfect planar graphs in parallel, Weak dynamic coloring of planar graphs, 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable, Disjoint total dominating sets in near‐triangulations, Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs, The amazing chromatic polynomial, Refined List Version of Hadwiger’s Conjecture, Towards the Chen-Raspaud conjecture, A strengthening and an efficient implementation of Alon-Tarsi list coloring method, Recent progress towards Hadwiger's conjecture, Partitioning a triangle-free planar graph into a forest and a forest of bounded degree, Some arithmetical restatements of the four color conjecture, Irreducible 4-critical triangle-free toroidal graphs, A generalized Beraha conjecture for non-planar graphs, Dynamic programming approach to the generalized minimum Manhattan network problem, Wildfire burn scar encapsulation. Subsetting common spatial domains for post-wildfire debris flow predictions over the United States, The choice number versus the chromatic number for graphs embeddable on orientable surfaces, On the dichromatic number of surfaces, Further extensions of the Grötzsch theorem, The fiber dimension of a graph, Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant, Circular backbone colorings: on matching and tree backbones of planar graphs, A heuristic for the coloring of planar graphs, Hadwiger's conjecture for squares of 2-trees, Defective 2-colorings of planar graphs without 4-cycles and 5-cycles, The construction and reduction of strong snarks, A categorical setting for the 4-colour theorem, Disproof of a conjecture by Woodall on the choosability of \(K_{s,t}\)-minor-free graphs, Conical \(\mathrm{SL}(3)\) foams, Mutual exclusion scheduling, Construction of fullerenes and Pogorelov polytopes with 5-, 6- and one 7-gonal face, Some remarks on even-hole-free graphs, The four-colour theorem, Graph coloring and semidefinite rank, On the minimal reducible bound for outerplanar and planar graphs, Facial \(L(2, 1)\)-edge-labelings of trees, On the precise value of the strong chromatic index of a planar graph with a large girth, On topological graphs with at most four crossings per edge, 3-coloring triangle-free planar graphs with a precolored 9-cycle, Colouring planar graphs with bounded monochromatic components, Five-list-coloring graphs on surfaces. III: One list of size one and one list of size two, The 2-factor polynomial detects even perfect matchings, New restrictions on defective coloring with applications to Steinberg-type graphs, Partitioning sparse graphs into an independent set and a graph with bounded size components, On generalized Heawood inequalities for manifolds: a van Kampen-Flores-type nonembeddability result, Colourings of graphs by labellings, Decomposition and \(r\)-hued coloring of \(K_4(7)\)-minor free graphs, Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable, Computer-assisted estimates for Birkhoff normal forms, Formally proving size optimality of sorting networks, The adjacent vertex distinguishing total choosability of planar graphs with maximum degree at least eleven, Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces, On Tutte's extension of the four-colour problem, Conflict-free coloring of intersection graphs of geometric objects, Monochromatic subgraphs in iterated triangulations, The set of vertices with positive curvature in a planar graph with nonnegative curvature, Chromatic optimisation: Limitations, objectives, uses, references, On the combinatorial problems which I would most like to see solved, On the cyclic coloring conjecture, Foam evaluation and Kronheimer-Mrowka theories, On the relationship between the biconnectivity augmentation and traveling salesman problems, A survey on the cyclic coloring and its relaxations, Variable neighborhood search for extremal graphs. V: Three ways to automate finding conjectures, Iterated colorings of graphs., Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests, Illuminating labyrinths., \(r\)-hued \((r+1)\)-coloring of planar graphs with girth at least 8 for \(r\geq 9\), Illuminating disjoint line segments in the plane, Heuristic for rapidly four-coloring large planar graphs, Finding a potential community in networks, Additive number theory via automata theory, Ising formulations of some graph-theoretic problems in psychological research: models and methods, Splitting a planar graph of girth 5 into two forests with trees of small diameter, Every plane graph is facially-non-repetitively \(C\)-choosable, The bounded chromatic number for graphs of genus \(g\), Choosability with union separation of triangle-free planar graphs, Ramsey-goodness -- and otherwise, Five-list-coloring graphs on surfaces. I. Two lists of size two in planar graphs, Near-colorings: non-colorable graphs and NP-completeness, Coloring squares of graphs with mad constraints, On the structure of \(k\)-connected graphs without \(K_{k}\)-minor, The complexity of the Hajós calculus for planar graphs, Decomposing a planar graph without triangular 4-cycles into a matching and a 3-colorable graph, Image segmentation by iterative optimization of multiphase multiple piecewise constant model and Four-Color relabeling, Differential algebra of cubic planar graphs, Differences between the list-coloring and DP-coloring for planar graphs, A curvature notion for planar graphs stable under planar duality, Colouring problems, On the vertex partition of planar graphs into forests with bounded degree, An adaptive, multiple restarts neural network algorithm for graph coloring, Topological invariants, multivalued maps and computer assisted proofs in dynamics, Open locating-dominating sets in circulant graphs, Facial rainbow coloring of plane graphs, On \(r\)-hued list coloring of \(K_4 ( 7 )\)-minor free graphs, Fractional colouring and Hadwiger's conjecture, Coloring drawings of graphs, Planar graphs without cycles of length 4 or 5 are \((11 : 3)\)-colorable, Planar graphs without pairwise adjacent 3-, 4-, 5-, and 6-cycle are 4-choosable, Planar Ramsey graphs, Towards the small quasi-kernel conjecture, A new bound on the cyclic chromatic number, Three moves on signed surface triangulations, Coloring face-hypergraphs of graphs on surfaces, Immersion and clustered coloring, Tutte paths and long cycles in circuit graphs, An \((F_3,F_5)\)-partition of planar graphs with girth at least 5, Computers and discovery in algebraic graph theory, Hadwiger's conjecture for \(K_ 6\)-free graphs, Realizing the chromatic numbers of triangulations of surfaces, A manifesto for the computational method, Flips signés et triangulations d'un polygone. (Signed flips and triangulations of a polygon), Partitioning planar graphs without 4-cycles and 6-cycles into a linear forest and a forest, Experimental results on quadrangulations of sets of fixed points, 1-planar graphs without 4-cycles or 5-cycles are 5-colorable, Lower bounds for constant degree independent sets
