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. This algorithm works when the odd girth is 7 or more. In this paper, we provide the following: for every ε > 0, there exists a constant g' ∈ {3, 5, 7, …} such that graphs with odd girth at least g' can be deterministically colored online using O(n^ε) colors.

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 conflicts between a pair of goods. Each agent is allocated an independent set in the graph. In a recent work of Kumar et al. (AAMAS, 2024), it was shown that a maximal EF1 allocation exists for interval graphs and two agents with monotone valuations. We significantly extend this result by establishing that a maximal EF1 allocation exists for any graph when the two agents have monotone valuations. To compute such an allocation, we present a polynomial-time algorithm for additive valuations, as well as a pseudo-polynomial time algorithm for monotone valuations. Moreover, we complement our findings by providing a counterexample demonstrating a maximal EF1 allocation may not exist for three agents with monotone valuations; further, we establish NP-hardness of determining the existence of such allocations for every fixed number n >= 3 of agents. All of our results for goods also apply to the allocation of chores.

We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. This is one of the most challenging problems in graph algorithms. In this paper using Blum’s notion of “progress”, we develop a new combinatorial algorithm for the following: Given any 3-colorable graph with minimum degree >√n, we can, in polynomial time, make progress towards a k-coloring for some k=√n/· no(1). We balance our main result with the best-known semi-definite(SDP) approach which we use for degrees below n0.605073. As a result, we show that (n0.19747) colors suffice for coloring 3-colorable graphs. This improves on the previous best bound of (n0.19996) by Kawarabayashi and Thorup from 2017.