Blog

(English translation of the original article mostly done by Gemini 3.1 Pro.) I attended the international conference IWOCA 2026 last week. Here is a quick overview of some of the talks I found interesting. Ad Our paper was presented by my coauthor Shunsuke Hamada (2nd-year master’s). We received the Best Student Paper award! Minimum Clique Bicoloring Shunsuke Hamada, Yuto Okada, Hirotaka Ono, Yota Otachi 📗Conference Version A clique coloring is a (not necessarily proper) vertex coloring such that every maximal clique contains at least two colors. It is known that many graph classes around perfect graphs are clique 2-colorable. In this paper, we introduced the problem of minimizing the number of colors on one side within a clique 2-coloring, and gave algorithms and hardness across various classes and parameters. ...

(English translation of the original article, by Gemini 3 Pro (~90%) + me.) This article is for the 21st day of Tree Advent Calendar 2025. Overview For a graph $G$, let $\mathrm{tw}(G)$ denote the treewidth of $G$. This article introduces a simple algorithm to solve the following decision problem. Input: A (simple undirected) graph $G = (V, E)$ with $n$ vertices and $m$ edges. Output: Is $\mathrm{tw}(G) \leq 3$? Expert readers might know these facts: ...