Search for: All records

Abstract We characterize Borel line graphs in terms of 10 forbidden induced subgraphs, namely the nine finite graphs from the classical result of Beineke together with a 10th infinite graph associated with the equivalence relation$$\mathbb {E}_0$$on the Cantor space. As a corollary, we prove a partial converse to the Feldman–Moore theorem, which allows us to characterize all locally countable Borel line graphs in terms of their Borel chromatic numbers. 

ABSTRACT 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. Intuitively, DP‐coloring generalizes list coloring by allowing the colors that are identified as the same to vary from edge to edge. Formally, DP‐coloring of a graph is equivalent to an independent transversal in an auxiliary structure called a DP‐cover of . In this paper, we introduce the notion of random DP‐covers and study the behavior of DP‐coloring from such random covers. We prove a series of results about the probability that a graph is or is not DP‐colorable from a random cover. These results support the following threshold behavior on random ‐fold DP‐covers as where is the maximum density of a graph: Graphs are non‐DP‐colorable with high‐probability when is sufficiently smaller than , and graphs are DP‐colorable with high‐probability when is sufficiently larger than . Our results depend on growing fast enough and imply a sharp threshold for dense enough graphs. For sparser graphs, we analyze DP‐colorability in terms of degeneracy. We also prove fractional DP‐coloring analogs to these results. 

We show that every Borel graph $G$of subexponential growth has a Borel proper edge-coloring with $\mathrm{\Delta <\#comment/>}\left(G\right)+1$colors. We deduce this from a stronger result, namely that an $n$-vertex (finite) graph $G$of subexponential growth can be properly edge-colored using $\mathrm{\Delta <\#comment/>}\left(G\right)+1$colors by an $O({\log }^{\ast <\#comment/>}<\#comment/>n)$-round deterministic distributed algorithm in theLOCALmodel, where the implied constants in the $O(\cdot <\#comment/>)$notation are determined by a bound on the growth rate of $G$.