Three papers co-authored by researchers from the National Institute of Informatics (NII; Director General: Sadao Kurohashi; Chiyoda-ku, Tokyo), an organization under the Research Organization of Information and Systems (ROIS), have been accepted to the 67th Annual Symposium on Foundations of Computer Science (FOCS 2026) *1 , a premier conference in theoretical computer science. Among them, a paper on the Four Color Theorem by Professor Ken-ichi Kawarabayashi of NII’s Principles of Informatics Research Division and his collaborators received the Best Paper Award.
[Summary]
Three papers co-authored by researchers from the National Institute of Informatics (NII) have been accepted at FOCS 2026 (The 67th Annual Symposium on Foundations of Computer Science; November 8-11, 2026, New York, USA), widely regarded as the world’s premier international conference in theoretical computer science. Among these, a paper by an international research team from Denmark, Canada, and Japan—including Professor Kawarabayashi—was honored with the Best Paper Award. The paper presents a novel proof of the Four Color Theorem *2 , which famously resolved the Four Color Problem first posed in 1852. Through this new proof, the researchers have achieved the first major efficiency breakthrough in approximately 30 years for computing 4-colorings of maps (planar graphs).
Best Paper Award: “The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring”
Yuta Inoue (The University of Tokyo), Ken-ichi Kawarabayashi (NII), Atsuyuki Miyashita (The University of Tokyo), Bojan Mohar (Simon Fraser University, Burnaby, Canada), Carsten Thomassen (Technical University of Denmark), Mikkel Thorup (University of Copenhagen)
The Four Color Theorem is a mathematical theorem stating that four colors are sufficient to color any map so that no two adjacent regions share the same color. First posed in 1852, it was proven in 1976 using a computer-assisted method that checked a vast number of cases. Today, the proof presented in 1996 by Robertson et al. is widely regarded as the standard. In this study, the researchers focused on reducible configurations and other simplifiable substructures used in the proof of the Four Color Theorem. While previous proofs only guaranteed the existence of at least one such configuration in any given map, this work revealed that they actually exist in quantities proportional to the size of the map. This insight enables the simultaneous simplification of multiple portions of a map. Consequently, the team developed an algorithm that substantially reduces the running time *3 for 4-coloring a map with n regions from the conventional O(n 2 ) to nearly linear time, approximately O( n log n ).
In addition, two other papers co-authored by Associate Professor Shuichi Hirahara of NII’s Principles of Informatics Research Division were accepted:
[Comment from Professor Ken-ichi Kawarabayashi]
“The Four Color Theorem is a celebrated research topic with a 175-year history, renowned not only within mathematics but across the entire scientific community. Furthermore, this year marks a historic milestone—the 50th anniversary of its resolution by Appel and Haken.
To achieve a lasting, landmark result on such a fundamental problem during this milestone year, together with my long-time international collaborators and my Ph.D. students, is deeply gratifying.”
Professor Ken-ichi Kawarabayashi – Researcher Profile: https://www.nii.ac.jp/en/faculty/informatics/kawarabayashi_kenichi/
Kawarabayashi Laboratory Website: https://kklab.nii.ac.jp/en/
(*1) FOCS 2026: An international conference sponsored by the IEEE Computer Society. Alongside STOC (ACM Symposium on Theory of Computing), it is widely recognized as one of the most prestigious conferences in the field of theoretical computer science.
https://focs.computer.org/2026/
(*2) The Four Color Theorem: A mathematical theorem stating that any planar map can be colored using at most four colors so that no two adjacent regions share the same color. First proposed in 1852, it was definitively proven in 1976.
(*3) Running Time (O(n2), O(n log n)): A notation indicating how the running time of a computation scales relative to the input size n. An algorithm with O(n2) complexity means that if n increases by a factor of 10, the required computation time grows roughly 100-fold. By contrast, under O(n log n), a 10-fold increase in n results in the computation time increasing by only slightly more than 10-fold.
[Related Links]
Quanta Magazine: "The Four-Color Theorem Gets a Rare New Proof"
https://www.quantamagazine.org/the-four-color-theorem-gets-a-rare-new-proof-20260910/
About the National Institute of Informatics (NII)
NII is Japan's only academic research institute dedicated to the new discipline of informatics. Its mission is to "create future value" in informatics. NII conducts both long-term basic research and practical research aimed at solving social problems in a wide range of informatics research fields, from fundamental theories to the latest topics, such as artificial intelligence, big data, the Internet of Things, and information security.
As an inter-university research institute, NII builds and operates academic information infrastructure essential for the research and educational activities of the entire academic community (including the Science Information Network) as well as developing services such as those that enable the provision of academic content and service platforms.
https://www.nii.ac.jp/en/
About the Research Organization of Information and Systems (ROIS)
ROIS is a parent organization of four national institutes (National Institute of Polar Research, National Institute of Informatics, the Institute of Statistical Mathematics and National Institute of Genetics) and the Joint Support-Center for Data Science Research. It is ROIS's mission to promote integrated, cutting-edge research that goes beyond the barriers of these institutions, in addition to facilitating their research activities, as members of inter-university research institutes.