The four-colour theorem

DOI10.1006/jctb.1997.1750zbMath0883.05056OpenAlexW2131433460WikidataQ55899217 ScholiaQ55899217MaRDI QIDQ1369648

Robin Thomas, Neil Robertson, P. D. Seymour, Daniel P. Sanders

Publication date: 16 March 1998

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/9a7262c7bb5e43d913bd6de2bf71fea9646565f2

zbMATH Keywords

planar graph vertex colouring four colour theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items

Bicircular matroids are 3-colorable, Three-edge-colouring doublecross cubic graphs, A proof via finite elements for Schiffer's conjecture on a regular pentagon, On purely tree-colorable planar graphs, Extending precolorings of subgraphs of locally 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, Building a maximal independent set for the vertex-coloring problem on planar graphs, A heuristic for the coloring of planar graphs, Facial incidence colorings of embedded multigraphs, Rotation invariant patterns for a nonlinear Laplace-Beltrami equation: a Taylor-Chebyshev series approach, Fullerene graphs have exponentially many perfect matchings, Subcubic planar graphs of girth 7 are class I, Uniquely forced perfect matching and unique 3-edge-coloring, Coloring immersion-free graphs, On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture, Contractions, cycle double covers, and cyclic colorings in locally connected graphs, Coloring octrees, Conflict-free coloring bounds on open neighborhoods, Graph coloring and semidefinite rank, On intersection representations of co-planar graphs, Approximate min-max relations for odd cycles in planar graphs, Some recent progress and applications in graph minor theory, Computing clique and chromatic number of circular-perfect graphs in polynomial time, 3-coloring triangle-free planar graphs with a precolored 9-cycle, Coloring Eulerian triangulations of the Klein bottle, Distance constraints in graph color extensions, A relaxed Hadwiger's conjecture for list colorings, On $r$-hued coloring of $K_4$-minor free graphs, The 2-factor polynomial detects even perfect matchings, Computer-aided proof of Erdős discrepancy properties, Decomposition and $r$-hued coloring of $K_4(7)$-minor free graphs, The complexity of changing colourings with bounded maximum degree, On dynamic coloring for planar graphs and graphs of higher genus, Arc diagrams, flip distances, and Hamiltonian triangulations, Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces, Light graphs in planar graphs of large girth, Polyhedron of triangle-free simple 2-matchings in subcubic graphs, Facial parity edge colouring of plane pseudographs, From the plane to higher surfaces, The set of vertices with positive curvature in a planar graph with nonnegative curvature, A survey on the cyclic coloring and its relaxations, Variable neighborhood search for extremal graphs. V: Three ways to automate finding conjectures, Randomly colouring graphs (a combinatorial view), Edge-disjoint odd cycles in planar graphs., Simpler multicoloring of triangle-free hexagonal graphs, On the 4-color theorem for signed graphs, Cyclic colorings of plane graphs with independent faces, Book review of: Alexander Soifer, The mathematical coloring book. Mathematics of coloring and the colorful life of its creators, Graph edge coloring: a survey, Edge-colouring seven-regular planar graphs, Edge-colouring eight-regular planar graphs, Coloring clique-hypergraphs of graphs with no subdivision of $K_5$, An introduction to the discharging method via graph coloring, Some remarks on the odd Hadwiger's conjecture, The $a$-graph coloring problem, The extremal function and Colin de Verdière graph parameter, Locally planar graphs are 5-choosable, Uncertain vertex coloring problem, Facial colorings using Hall's theorem, Injective colorings of graphs with low average degree, On degrees in random triangulations of point sets, On the structure of $k$-connected graphs without $K_{k}$-minor, Cyclic, diagonal and facial colorings, Random planar graphs, Rotation sequences and edge-colouring of binary tree pairs, Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight, A simple algorithm for 4-coloring 3-colorable planar graphs, A revision of the proof of the Kepler conjecture, Contractibility and the Hadwiger conjecture, Five-coloring graphs on the Klein bottle, Maximal distance spectral radius of 4-chromatic planar graphs, Spontaneous periodic orbits in the Navier-Stokes flow, A bound on the treewidth of planar even-hole-free graphs, A curvature notion for planar graphs stable under planar duality, Representing graphs as the intersection of cographs and threshold graphs, Automated generation of conjectures on forbidden subgraph characterization, Nowhere-zero 4-flow in almost Petersen-minor free graphs, The edge version of Hadwiger's conjecture, 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, On $r$-hued list coloring of $K_4 ( 7 )$-minor free graphs, List-coloring graphs without $K_{4,k}$-minors, The Voronoi diagram of three lines, Clique minors in claw-free graphs, Fractional colouring and Hadwiger's conjecture, Global dynamics in nonconservative nonlinear Schrödinger equations, Cliques, minors and apex graphs, Bicubic planar maps, Edge colorings of graphs embeddable in a surface of low genus, On cyclic colorings and their generalizations, Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds, Surfaces, tree-width, clique-minors, and partitions, A new bound on the cyclic chromatic number, Planar graphs of maximum degree seven are Class I, Coloring the faces of convex polyhedra so that like colors are far apart, Immersion and clustered coloring, Tutte paths and long cycles in circuit graphs, Computers and discovery in algebraic graph theory, Properties of chromatic polynomials of hypergraphs not held for chromatic polynomials of graphs, Clustered 3-colouring graphs of bounded degree, On computer-assisted proving the existence of periodic and bounded orbits, Light structures in infinite planar graphs without the strong isoperimetric property, Homomorphism bounded classes of graphs, The $d$-precoloring problem for $k$-degenerate graphs, Hamilton weights and Petersen minors, The number of defective colorings of graphs on surfaces, Formalizing Frankl’s Conjecture: FC-Families, Six-Critical Graphs on the Klein Bottle, The justification of mathematical statements, Unnamed Item, Cyclic 4-Colorings of Graphs on Surfaces, Conflict-Free Coloring of Graphs, Introduction to rigorous numerics in dynamics: General functional analytic setup and an example that forces chaos, Transfer matrices and partition-function zeros for antiferromagnetic Potts models. V. Further results for the square-lattice chromatic polynomial, Hyperbolic families and coloring graphs on surfaces, Cyclically five-connected cubic graphs, Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs, Facially-constrained colorings of plane graphs: a survey, Cyclic coloring of plane graphs with maximum face size 16 and 17, 3-Coloring Triangle-Free Planar Graphs with a Precolored 9-Cycle, Checking Proofs, Hadwiger's Conjecture for Graphs with Forbidden Holes, Proper orientations and proper chromatic number, Coloring count cones of planar graphs, 4‐Separations in Hajós graphs, Packing Signatures in Signed Graphs, Computer Bounds for Kronheimer–Mrowka Foam Evaluation, Dual circumference and collinear sets, Even-hole-free planar graphs have bounded treewidth, Transformation invariance in the combinatorial Nullstellensatz and nowhere-zero points of non-singular matrices, Approximating maximum integral multiflows on bounded genus graphs, Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs, Strengthening a Theorem of Meyniel, Unnamed Item, List 4-colouring of planar graphs, Refined List Version of Hadwiger’s Conjecture, Epistemic injustice in mathematics, Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor, Experimental mathematics, computers and the a priori, Polynomial hierarchy graph properties in hybrid logic, RECONSTRUCTING CONVEX POLYGONS AND CONVEX POLYHEDRA FROM EDGE AND FACE COUNTS IN ORTHOGONAL PROJECTIONS, Spanning cycles in regular matroids without $M^{*}(K_{5})$ minors, Chromatic numbers of quadrangulations on closed surfaces, One More Probabilistic Reformulation of the Four Colour Conjecture, Fractional coloring and the odd Hadwiger's conjecture, Five-list-coloring graphs on surfaces. I. Two lists of size two in planar graphs, Some arithmetical restatements of the four color conjecture, Grünbaum colorings of toroidal triangulations, The Maximum Independent Set Problem in Planar Graphs, Colouring Random Empire Trees, Unnamed Item, Conditional colorings of graphs, Coloring plane graphs with independent crossings, Irreducible 4-critical triangle-free toroidal graphs, A Weakening of the Odd Hadwiger's Conjecture, Spanning embeddings of arrangeable graphs with sublinear bandwidth, PARTIAL RESULT ON HADWIGER'S CONJECTURE, Third Case of the Cyclic Coloring Conjecture, An unavoidable set of $D$-reducible configurations, Large Independent Sets in Subquartic Planar Graphs, Large Independent Sets in Triangle-Free Planar Graphs, Dynamic programming approach to the generalized minimum Manhattan network problem, Facial rainbow coloring of plane graphs, On Tutte’s chromatic invariant, An Approximation Algorithm for Fully Planar Edge-Disjoint Paths, Subcubic triangle-free graphs have fractional chromatic number at most 14/5, Unnamed Item, COLORING PLANAR GRAPHS VIA COLORED PATHS IN THE ASSOCIAHEDRA, Kempe-locking configurations, Transition polynomials, Graphs, friends and acquaintances, Unique-maximum edge-colouring of plane graphs with respect to faces, Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles, Unnamed Item, Towards an algorithmic guide to Spiral Galaxies, Randomized Δ-edge colouring via exchanges of complex colours, Extremal functions for sparse minors, There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration

Cites Work