Four-Coloring Planar Graphs in Linear Time
Auteurs : Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen, Mikkel Thorup
Résumé scientifique
The famous Four Color Theorem (4CT) states that any planar graph can be colored with four colors, but how do we find a 4-coloring? In our previous paper [FOCS'26], we presented a simple combinatorial algorithm to 4-color planar graphs in $O(n\log n)$ time. We improve it here to $O(n)$ time, which is optimal. The algorithm from our previous paper is based on proving that every planar triangulation has a linear number of reducible configurations or obstructing cycles. The bottleneck for the algorithm is that we need $O(\log n)$ Kempe changes to extend a recursive 4-coloring to the reducible configurations. Each Kempe change can involve a constant fraction of the graph and takes linear time. Here we show that all $O(\log n)$ Kempe changes can be identified and implemented in $O(n)$ time. The idea is to spend $O(n)$ time to preprocess the graph so that we can identify and simulate each good Kempe change in $O(n/\log n)$ amortized time. Thus, we implement all $O(\log n)$ Kempe changes in $O(n)$ total time. Based on this, we implement the whole 4-coloring in linear time. We note that creating such a representation for fast identification and simulation of the right Kempe changes is a challenge of data structures, unlike the previous paper that builds on a new graph theoretic understanding of reducible configurations.
Les articles autour de lui, par date et par proximité
Plus haut, c’est plus proche de cet article ; à gauche, c’est plus ancien. Les traits relient les articles proches entre eux : les groupes de traits sont des sous-thèmes. Sélectionnez un point pour voir pourquoi il est là. Retour au résumé de cet article
Les articles autour de celui-ci
Classés selon la proximité de leur titre et de leur résumé avec ceux de cet article. Sélectionnez-en pour les lire ensemble.
Les articles les plus proches
-
Three-coloring triangle-free planar graphs in linear timeZ. Dvořák, K. Kawarabayashi, R. Thomas · 2009 · TALG · cité 45 fois · Pas encore résumé
Three-coloring triangle-free planar graphs in linear time construit en temps linéaire une 3-coloration, tandis que l’article traite la 4-coloration de graphes planaires.
Résumé scientifique
Grötzsch's theorem states that every triangle-free planar graph is 3-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to convert these proofs into quadratic-time algorithms to find a 3-coloring, but it is not clear how to find such a coloring in linear time (Kowalik used a nontrivial data structure to construct an O(n log n) algorithm). We design a linear-time algorithm to find a 3-coloring of a given triangle-free planar graph. The algorithm avoids using any complex data structures, which makes it easy to implement. As a by-product, we give a yet simpler proof of Grötzsch's theorem.
-
Efficiently four-coloring planar graphsN. Robertson, Daniel P. Sanders, P. Seymour et al. · 1996 · Symposium on the Theory of Computing · cité 124 fois · Pas encore résumé
Efficiently four-coloring planar graphs traite la construction d’une 4-coloration de graphes planaires.
-
Three-coloring triangle-free planar graphs in linear time (extended abstract)Z. Dvořák, Ken-ichi Kawarabayashi, Robin Thomas · 2009 · cité 1 fois · Pas encore résumé
Three-coloring triangle-free planar graphs in linear time (extended abstract) porte sur une 3-coloration linéaire de graphes planaires sans triangles.
-
Deciding 4-colorability of planar triangulationsM. Loebl · 2015 · arXiv.org · preprint, non relu par les pairs · cité 1 fois · Pas encore résumé
Deciding 4-colorability of planar triangulations étudie la 4-colorabilité des triangulations planaires, mais décide son existence plutôt que de construire une coloration.
Résumé scientifique
We show, without using the Four Color Theorem, that for each planar triangulation, the number of its proper vertex colorings by 4 colors is a determinant and thus can be calculated in a polynomial time. In particular, we can efficiently decide if the number is non-zero.
-
A simple algorithm for 4-coloring 3-colorable planar graphsK. Kawarabayashi, K. Ozeki · 2010 · Theoretical Computer Science · cité 6 fois · Pas encore résumé
A simple algorithm for 4-coloring 3-colorable planar graphs porte sur la coloration de graphes planaires avec quatre couleurs, sous une restriction de 3-colorabilité.
-
Every Planar Map Is Four ColorableK. Appel, W. Haken · 2019 · Mathematical Solitaires & Games · cité 656 fois · Pas encore résumé
Every Planar Map Is Four Colorable établit le théorème des quatre couleurs et s’appuie sur la réductibilité, utilisée par l’article pour construire sa coloration.
Résumé scientifique
As has become standard, the four color map problem will be considered in the dual sense as the problem of whether the vertices of every planar graph (without loops) can be colored with at most four colors in such a way that no pair of vertices which lie on a common edge have the same color. The restriction to triangulations with all vertices of degree at least five is a consequence of the work of A. B. Kempe. Over the past 100 years, a number of authors including A. B. Kempe, G. D. Birkhoff, and H. Heesch have developed a theory of reducibility to attack the problem. Simultaneously, a theory of unavoidable sets has been developed and the fusion of these has led to the proof. A configuration …
-
3-Coloring in Time O(1.3217^n)Lucas Meijer · 2023 · arXiv.org · preprint, non relu par les pairs · cité 16 fois · Pas encore résumé
3-Coloring in Time O(1.3217^n) propose un algorithme de 3-coloration pour des graphes, mais pas spécifiquement des graphes planaires.
Résumé scientifique
We propose a new algorithm for 3-coloring that runs in time O(1.3217^n). For this algorithm, we make use of the time O(1.3289^n) algorithm for 3-coloring by Beigel and Eppstein. They described a structure in all graphs, whose vertices could be colored relatively easily. In this paper, we improve upon this structure and present new ways to determine how the involved vertices reduce the runtime of the algorithm.
-
Drawing 2-, 3- and 4-colorable Graphs in O(n2) VolumeT. Calamoneri, Andrea Sterbini · 1996 · International Symposium Graph Drawing and Network Visualization · cité 15 fois · Pas encore résumé
Drawing 2-, 3- and 4-colorable Graphs in O(n2) Volume étudie le dessin de graphes colorables, plutôt que la construction d’une coloration planaire.
Les travaux antérieurs sur lesquels il s’appuie
-
Structured recursive separator decompositions for planar graphs in linear timeP. Klein, S. Mozes, Christian Sommer · 2012 · Symposium on the Theory of Computing · cité 92 fois · Pas encore résumé
Structured recursive separator decompositions for planar graphs in linear time calcule en temps linéaire des décompositions récursives de graphes planaires, utiles aux divisions de l’article.
Résumé scientifique
Given a triangulated planar graph G on n vertices and an integer rr--division of G with few holes is a decomposition of G into O(n/r) regions of size at most r such that each region contains at most a constant number of faces that are not faces of G (also called holes), and such that, for each region, the total number of vertices on these faces is O(√ r). We provide an algorithm for computing r--divisions with few holes in linear time. In fact, our algorithm computes a structure, called decomposition tree, which represents a recursive decomposition of G that includes r--divisions for essentially all values of r. In particular, given an exponentially increasing sequence {vec r} = (r1,r2,...),…
-
EVERY PLANAR MAP IS FOUR COLORABLERobin J. Wilson · 1991 · Bulletin of The London Mathematical Society · cité 319 fois · Pas encore résumé
EVERY PLANAR MAP IS FOUR COLORABLE énonce le théorème des quatre couleurs, fondement du problème traité par l’article.
-
The Four-Color ProblemK. Appel, W. Haken · 1978 · cité 254 fois · Pas encore résumé
The Four-Color Problem traite le problème des quatre couleurs auquel l’article apporte un algorithme de construction en temps linéaire.
-
An unavoidable set of D-reducible configurationsJ. Steinberger · 2009 · arXiv: Combinatorics · preprint, non relu par les pairs · cité 11 fois · Pas encore résumé
An unavoidable set of D-reducible configurations établit un ensemble inévitable de configurations D-réductibles, notion reprise dans l’algorithme de l’article.
Résumé scientifique
We give a new proof of the four-color theorem by exhibiting an unavoidable set of 2822 D-reducible configurations. The existence of such a set had been conjectured by several researchers including Stromquist, Appel and Haken, and Robertson, Sanders, Seymour and Thomas.
-
Fast Algorithms for Shortest Paths in Planar Graphs, with ApplicationsG. Frederickson · 1987 · SIAM journal on computing (Print) · cité 492 fois · Pas encore résumé
Fast Algorithms for Shortest Paths in Planar Graphs, with Applications fournit des méthodes pour les graphes planaires citées par l’article, sans traiter leur coloration.
Aller plus loin
Comment ces articles sont-ils trouvés ?
Nous comparons le titre et le résumé de cet article avec ceux de tous les articles résumés sur ce site, et avec les articles que Semantic Scholar recommande, ceux qu’il cite et ceux qui le citent (pour un article très cité, ses citations les plus récentes et, depuis OpenAlex, les plus citées). Parmi les travaux antérieurs et les suites, les articles qui s’utilisent en profondeur, une méthode qu’il utilise et les suites très citées remontent un peu. Les niveaux (très proche, proche, apparenté) viennent de la similarité des textes, pas d’un jugement de qualité ; * signale un article sans résumé, comparé par son titre. La phrase sous un article est écrite par une IA à partir des deux résumés : vérifiez-la dans les articles. Un article jugé hors sujet par trois lecteurs quitte la liste.
Mis à jour le 2 novembre 2026.