Masataka Yoneda

collaborators

4 papers

cs.DS2026

The Balanced Four-Color Theorem

Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda

We show that every planar graph with $n \geq 3$ vertices admits a 4-coloring in which each color is used on fewer than $n /2$ vertices. This bound is the best possible. Moreover, su…

cs.DS2026

Online Coloring for Graphs of Large Odd Girth

Hirotaka Yoneda, Masataka Yoneda

We study the problem of online coloring for graphs with large odd girth. The best previously known algorithm uses $O (n^{1/2})$ colors, which was discovered by Kierstead in 1998. Th…

cs.GT2026

Fair Division with Soft Conflicts

Hirotaka Yoneda, Masataka Yoneda

We study the fair division of indivisible goods with conflicts between pairs of goods, represented by a graph $G = (V, E)$ . We consider ``soft'' conflicts: assigning two adjacent g…

cs.DS2025

Online Graph Coloring for $k$ -Colorable Graphs