A. Dhawan

collaborators

3 papers

math.CO2023

Multigraph edge-coloring with local list sizes

Abhishek Dhawan

Let $G$ be a multigraph and $L : E (G) \to 2^{N}$ be a list assignment on the edges of $G$ . Suppose additionally, for every vertex $x$ , the edges incident to $x$ have at le…

cs.DS2023

Edge-Coloring Algorithms for Bounded Degree Multigraphs

Abhishek Dhawan

In this paper, we consider algorithms for edge-coloring multigraphs $G$ of bounded maximum degree, i.e., $Δ (G) = O (1)$ . Shannon's theorem states that any multigraph of maximum degr…

math.CO2023

Borel Vizing's Theorem for Graphs of Subexponential Growth

Anton Bernshteyn, Abhishek Dhawan

We show that every Borel graph $G$ of subexponential growth has a Borel proper edge-coloring with $Δ (G) + 1$ colors. We deduce this from a stronger result, namely that an $n$ -verte…