6 papers · 1 filter
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…
Graph Coloring with Color Preferences
Tomohiro Koana, Yeeseok Oh, Hirotaka Yoneda
We study graph coloring with color preferences, in which each vertex ranks the available colors. In addition to assigning different colors to adjacent vertices, we require the colo…
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…
Fair Allocation under Conflict Constraints
Sarfaraz Equbal, Rohit Gurjar, Ayumi Igarashi +6
We study the fair allocation of indivisible items subject to conflict constraints. In this framework, the items are represented as the vertices of a graph, with edges corresponding…
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…