From the 1 of 4 linked papers with an AI index.
4 papers
The Balanced Four-Color Theorem
Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
The paper proves that every planar graph with at least three vertices can be 4‑colored so that each color class contains fewer than half of the vertices, and provides an O(n log n)…
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 colors, which was discovered by Kierstead in 1998. Th…
Online Graph Coloring for -Colorable Graphs
Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
We study the problem of online graph coloring for -colorable graphs. The best previously known deterministic algorithm uses colors for genera…
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 . We consider ``soft'' conflicts: assigning two adjacent g…