Every planar map is four colorable. II: Reducibility

Related Items

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, 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, The k-conversion number of regular graphs, Dynamic programming approach to the generalized minimum Manhattan network problem, 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, Third case of the cyclic coloring conjecture, Simultaneously colouring the edges and faces of plane graphs, Coloring immersion-free graphs, How robust is the n-cube?, On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture, Optimal-depth sorting networks, 5-list-coloring planar graphs with distant precolored vertices, The four-colour theorem, 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 Penrose number of cubic diagrams, List homomorphisms to reflexive 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, On 1-improper 2-coloring of sparse graphs, The book thickness of a graph, Toward a language theoretic proof of the four color theorem, $(k,1)$-coloring of sparse graphs, Hadwiger's conjecture for graphs on the Klein bottle, $(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, Objects and processes in mathematical practice, On a generalization of ``eight blocks to madness puzzle, Computer-assisted proof of performance ratios for the differencing method, On Tutte's extension of the four-colour problem, Euler index in uncertain graph, On the relationship between the biconnectivity augmentation and traveling salesman problems, Randomly colouring graphs (a combinatorial view), Strong chromatic index of planar graphs with large girth, Zero-sum flows of the linear lattice., Simpler multicoloring of triangle-free hexagonal graphs, On the tractability of some natural packing, covering and partitioning problems, Can strategizing in round-robin subtournaments be avoided?, Heuristic for rapidly four-coloring large planar graphs, 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, Modernizing the philosophy of mathematics, 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, An introduction to the discharging method via graph coloring, Some remarks on the odd Hadwiger's conjecture, 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, Binary pattern tile set synthesis is NP-hard, A new clustering algorithm for coordinate-free data, 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, The thickness and chromatic number of $r$-inflated graphs, Five-coloring graphs on the Klein bottle, Graph theory (algorithmic, algebraic, and metric problems), Planar graphs without 4-cycles and close triangles are $(2,0,0)$-colorable, Looseness and independence number of triangulations on closed surfaces, Colouring problems, List coloring the square of sparse graphs with large degree, Automated generation of conjectures on forbidden subgraph characterization, 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, Clique minors in claw-free graphs, Connected greedy coloring of $H$-free graphs, 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, Efficient bounds for the stable set, vertex cover and set packing problems, Hadwiger's conjecture for $K_ 6$-free graphs, Heawood's empire problem, Realizing the chromatic numbers of triangulations of surfaces, The four color proof suffices, Lower bounds for constant degree independent sets, Regular independent sets, The choice number versus the chromatic number for graphs embeddable on orientable surfaces, Every planar graph without cycles of length 4 or 9 is $(1, 1, 0)$-colorable, Further extensions of the Grötzsch theorem, On computer-assisted proving the existence of periodic and bounded orbits, 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, Oriented incidence colourings of digraphs, Hadwiger's conjecture for squares of 2-trees, Defective 2-colorings of planar graphs without 4-cycles and 5-cycles, A categorical setting for the 4-colour theorem, A blow-up construction and graph coloring, Disproof of a conjecture by Woodall on the choosability of $K_{s,t}$-minor-free graphs, Construction of fullerenes and Pogorelov polytopes with 5-, 6- and one 7-gonal face, Some remarks on even-hole-free graphs, Graph coloring and semidefinite rank, On star 5-colorings of sparse graphs, On $t$-common list-colorings, Facially-constrained colorings of plane graphs: a survey, Triangle-free graphs of tree-width $t$ are $\lceil (t+3)/2 \rceil$-colorable, 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, 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$, 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, Facial $[r,s,t$-colorings of plane 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, Ugly mathematics: why do mathematicians dislike computer-assisted proofs?, Decomposition and $r$-hued coloring of $K_4(7)$-minor free graphs, On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree, Computer-assisted estimates for Birkhoff normal forms, Formally proving size optimality of sorting networks, 4-choosability of planar graphs with 4-cycles far apart via the Combinatorial Nullstellensatz, The adjacent vertex distinguishing total choosability of planar graphs with maximum degree at least eleven, Sketchy tweets: ten minute conjectures in graph theory, 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, Conflict-free coloring of intersection graphs of geometric objects, Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor, Properties of 8-contraction-critical graphs with no $K_7$ minor, Monochromatic subgraphs in iterated triangulations, Experimental mathematics, computers and the a priori, On the cyclic coloring conjecture, Foam evaluation and Kronheimer-Mrowka theories, A survey on the cyclic coloring and its relaxations, Variable neighborhood search for extremal graphs. V: Three ways to automate finding conjectures, Planar graphs with cycles of length neither 4 nor 6 are $(2,0,0)$-colorable, Dynamic coloring and list dynamic coloring of planar graphs, Iterated colorings of graphs., Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests, Illuminating labyrinths., $(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, $r$-hued $(r+1)$-coloring of planar graphs with girth at least 8 for $r\geq 9$, Illuminating disjoint line segments in the plane, Spanning cycles in regular matroids without $M^{*}(K_{5})$ minors, Additive number theory via automata theory, Fractional coloring and the odd Hadwiger's conjecture, Generating even triangulations on the torus, Splitting a planar graph of girth 5 into two forests with trees of small diameter, Every plane graph is facially-non-repetitively $C$-choosable, 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, The surveyability of long proofs, Decomposing a planar graph without triangular 4-cycles into a matching and a 3-colorable graph, Conditional colorings of graphs, Pushing the frontier of minimality, Differential algebra of cubic planar graphs, Third Case of the Cyclic Coloring Conjecture, Coloring $d$-embeddable $k$-uniform hypergraphs, On the vertex partition of planar graphs into forests with bounded degree, Hadwiger’s Conjecture and Squares of Chordal Graphs, Topological invariants, multivalued maps and computer assisted proofs in dynamics, 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 pairwise adjacent 3-, 4-, 5-, and 6-cycle are 4-choosable, Planar graphs with girth at least 5 are $(3, 4)$-colorable, Towards the small quasi-kernel conjecture, Kempe-locking configurations, Three moves on signed surface triangulations, 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, 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, 1-planar graphs without 4-cycles or 5-cycles are 5-colorable