Skip to content

Author

K. Kawarabayashi

We have 2 of 21 papers

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Oct 2026

An $O(n^{0.1537})$-Coloring Algorithm for 3-Colorable Graphs

We present a polynomial-time randomized algorithm that colors every $n$-vertex $3$-colorable graph with $O(n^{0.1537})$ colors. This improves upon the previous bound of $O(n^{0.1954})$ colors by Bansal, Huang, and Lee (SODA'27). To achieve this result, we introduce a new algorithmic framework for finding a large indepe...

Kaisei Deguchi, K. Kawarabayashi, Hirotaka Yoneda et al. · 0 citations
Preprint Aug 2026

Three-edge-coloring apex cubic graphs

A graph $G$ is \emph{apex} if $G$ has a vertex $v$ such that $G-v$ is planar. We prove that every $2$-connected apex cubic graph is three-edge-colorable. This result gives the final piece of the proof for the well-known Tutte's three-edge-coloring conjecture from 1966 \cite{tutte}. The proof, as well as the result, gen...

Yuta Inoue, K. Kawarabayashi, Rintaro Matsuo et al. · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.