6 papers
Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic Algorithms
Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
We study online coloring, focusing on the competitive ratio. The best previously known results were (1) a lower bound of for both deterministic and randomized alg…
A Sub- Upper Bound on the Number of Stable Matchings
Ken-ichi Kawarabayashi, Hikaru Wada, Masataka Yoneda
We study the problem of determining the maximum number of stable matchings. This classical counting problem was posed by Knuth and has been studied for five decades. We obtain a ne…
The Balanced Four-Color Theorem
Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
We show that every planar graph with vertices admits a 4-coloring in which each color is used on fewer than vertices. This bound is the best possible. Moreover, su…
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…
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…
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…