A. Dhawan

collaborators

3 papers

cs.DS2025

Fast algorithms for Vizing's theorem on bounded degree graphs

Anton Bernshteyn, Abhishek Dhawan

Vizing's theorem states that every graph $G$ of maximum degree $I^$ can be properly edge-colored using $I^ + 1$ colors. The fastest currently known $(I^ + 1)$ -edge-coloring algorithm…

math.CO2025

Coloring graphs with forbidden almost bipartite subgraphs

James Anderson, Anton Bernshteyn, Abhishek Dhawan

Alon, Krivelevich, and Sudakov conjectured in 1999 that for every finite graph $F$ , there exists a quantity $c (F)$ such that $I ¨ (G) \leq (c (F) + o (1)) I^/ lo g I^$ whenever $G$ is a…

math.CO2025

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…