Every planar map is four colorable. II: Reducibility

zbMath0387.05010MaRDI QIDQ1250224

K. Appert

Publication date: 1977

Published in: Illinois Journal of Mathematics (Search for Journal in Brave)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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

Improved lower bound for the list chromatic number of graphs with no K_t minor ⋮ Overlapping Domain Decomposition Preconditioner for Integral Equations ⋮ Unnamed Item ⋮ Six-Critical Graphs on the Klein Bottle ⋮ The challenge of computer mathematics ⋮ 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 ⋮ 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 ⋮ Checking Proofs ⋮ Hadwiger's Conjecture for Graphs with Forbidden Holes ⋮ 1-planar graphs are odd 13-colorable ⋮ Inductive graph invariants and approximation algorithms ⋮ Wheels in planar graphs and Hajós graphs ⋮ An (F1,F4)‐partition of graphs with low genus and girth at least 6 ⋮ 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 ⋮ Transformation invariance in the combinatorial Nullstellensatz and nowhere-zero points of non-singular matrices ⋮ 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 ⋮ 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 ⋮ Unnamed Item ⋮ Towards the Chen-Raspaud conjecture ⋮ A strengthening and an efficient implementation of Alon-Tarsi list coloring method ⋮ Recent progress towards Hadwiger's conjecture ⋮ Graphs of large chromatic number ⋮ Unnamed Item ⋮ Nowhere–zero bases for the nullspace of the incidence matrices of graphs ⋮ Hadwiger's conjecture for quasi-line graphs ⋮ (1,k)-Coloring of Graphs with Girth at Least Five on a Surface ⋮ Computation in Causal Graphs ⋮ Partitioning a triangle-free planar graph into a forest and a forest of bounded degree ⋮ 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 ⋮ Proper conflict-free coloring of sparse graphs ⋮ Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks ⋮ Some arithmetical restatements of the four color conjecture ⋮ Grünbaum colorings of toroidal triangulations ⋮ 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 ⋮ Irreducible 4-critical triangle-free toroidal graphs ⋮ Elli Heesch, Heinrich Heesch and Hilbert’s eighteenth problem: collaborative research between philosophy, mathematics and application ⋮ The k-conversion number of regular graphs ⋮ Partitioning planar graph of girth 5 into two forests with maximum degree 4. ⋮ Planar graphs without 4- and 6-cycles are \(( 3 , 4 )\)-colorable ⋮ A sufficient condition for planar graphs with girth 5 to be \((1,6)\)-colorable ⋮ Introduction to competitive graph coloring ⋮ ``The end of proof? The integration of different mathematical cultures as experimental mathematics comes of age ⋮ Dynamic programming approach to the generalized minimum Manhattan network problem ⋮ The high order spectral extremal results for graphs and their applications ⋮ On locating and neighbor-locating colorings of sparse graphs ⋮ Discrete geometry. Abstracts from the workshop held January 21--26, 2024 ⋮ On the choosability of \(H\)-minor-free graphs ⋮ Graph coloring and semidefinite rank ⋮ Unimodal sequences: from Isaac Newton to June Huh ⋮ Rock extensions with linear diameters ⋮ Coloring zonotopal quadrangulations of the projective space ⋮ Theory of Quantum Computation and Philosophy of Mathematics. Part II ⋮ Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths ⋮ Large Induced Forests in Graphs ⋮ Hadwiger’s Conjecture ⋮ CATEGORY-BASED CO-GENERATION OF SEMINAL CONCEPTS AND RESULTS IN ALGEBRA AND NUMBER THEORY: CONTAINMENT-DIVISION AND GOLDBACH RINGS ⋮ On BMRN*-colouring of planar digraphs ⋮ $$\textit{\textbf{k}}$$-Planar Graphs ⋮ Computers as a Source of A Posteriori Knowledge in Mathematics ⋮ Graphs, friends and acquaintances ⋮ COMPUTER TOOLS FOR SOLVING MATHEMATICAL PROBLEMS: A REVIEW ⋮ Unnamed Item ⋮ 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 ⋮ 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 ⋮ A note on the minimum cut cover of 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

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