6 papers · 1 filter
On strongly and robustly critical graphs
Anton Bernshteyn, Hemanshu Kaul, Jeffrey A. Mudrock +1
In extremal combinatorics, it is common to focus on structures that are minimal with respect to a certain property. In particular, critical and list-critical graphs occupy a promin…
Weak Degeneracy of Planar Graphs
Anton Bernshteyn, Eugene Lee, Evelyne Smith-Roberge
The weak degeneracy of a graph is a numerical parameter that was recently introduced by the first two authors with the aim of understanding the power of greedy algorithms for g…
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 , there exists a quantity such that whenever is a…
Large-scale geometry of Borel graphs of polynomial growth
Anton Bernshteyn, Jing Yu
We study graphs of polynomial growth from the perspective of asymptotic geometry and descriptive set theory. The starting point of our investigation is a theorem of Krauthgamer and…
DP-Coloring of Graphs from Random Covers
Anton Bernshteyn, Daniel Dominik, Hemanshu Kaul +1
DP-coloring (also called correspondence coloring) of graphs is a generalization of list coloring that has been widely studied since its introduction by DvoÅák and Postle in $2015…
Borel Vizing's Theorem for Graphs of Subexponential Growth
Anton Bernshteyn, Abhishek Dhawan
We show that every Borel graph of subexponential growth has a Borel proper edge-coloring with colors. We deduce this from a stronger result, namely that an -vert…