Showing 2025Show all
2 papers · 1 filter
cs.DS2025
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…
cs.GT2025
Dividing Conflicting Items Fairly
Ayumi Igarashi, Pasin Manurangsi, Hirotaka Yoneda
We study the allocation of indivisible goods under conflicting constraints, represented by a graph. In this framework, vertices correspond to goods and edges correspond to conflict…