Search

ABSTRACT If L $L$ is a list assignment of r $r$ colors to each vertex of an n $n$‐vertex graph G $G$, then an equitable L $L$‐coloring of G $G$ is a proper coloring of vertices of G $G$ from their lists such that no color is used more than ⌈n/r⌉ $\lceil n/r\rceil $ times. A graph is equitably r $r$‐choosable if it has an equitable L $L$‐coloring for every r $r$‐list assignment L $L$. In 2003, Kostochka, Pelsmajer, and West (KPW) conjectured that an analog of the famous Hajnal–Szemerédi Theorem on equitable coloring holds for equitable list coloring, namely, that for each positive integer r $r$ every graph G $G$ with maximum degree at most r−1 $r-1$ is equitably r $r$‐choosable. The main result of this paper is that for each r≥9 $r\ge 9$ and each planar graph G $G$, a stronger statement holds: if the maximum degree of G $G$ is at most r $r$, then G $G$ is equitably r $r$‐choosable. In fact, we prove the result for a broader class of graphs—the class ℬ ${\rm{ {\mathcal B} }}$ of the graphs in which each bipartite subgraph B $B$ with |V(B)|≥3 $|V(B)|\ge 3$ has at most 2|V(B)|−4 $2|V(B)|-4$ edges. Together with some known results, this implies that the KPW Conjecture holds for all graphs in ℬ ${\rm{ {\mathcal B} }}$, in particular, for all planar graphs. We also introduce the new stronger notion of strongly equitable (SE, for short) list coloring and prove all bounds for this parameter. An advantage of this is that if a graph is SE r $r$‐choosable, then it is both equitably r $r$‐choosable and equitably r $r$‐colorable, while neither of being equitably r $r$‐choosable and equitably r $r$‐colorable implies the other. [ABSTRACT FROM AUTHOR]

In the language of hypergraphs, our main result is a Dirac‐type bound: We prove that every 3‐connected hypergraph ℋ with δ(H)≥max{∣V(H)∣,∣E(H)∣+ 104} has a hamiltonian Berge cycle. This is sharp and refines a conjecture by Jackson from 1981 (in the language of bipartite graphs). Our proofs are in the language of bipartite graphs, since the incidence graph of each hypergraph is bipartite. [ABSTRACT FROM AUTHOR]

DP‐coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvořák and Postle [J. Combin. Theory Ser. B 129 (2018), pp. 38–54]. In this paper we introduce and study the fractional DP‐chromatic number χDP*(G). We characterize all connected graphs G such that χDP*(G)⩽2: they are precisely the graphs with no odd cycles and at most one even cycle. By a theorem of Alon, Tuza, and Voigt [Discrete Math. 165–166 (1997), pp. 31–38], the fractional list‐chromatic number χℓ*(G) of any graph G equals its fractional chromatic number χ*(G). This equality does not extend to fractional DP‐colorings. Moreover, we show that the difference χDP*(G)−χ*(G) can be arbitrarily large, and, furthermore, χDP*(G)⩾d∕(2lnd) for every graph G of maximum average degree d⩾4. On the other hand, we show that this asymptotic lower bound is tight for a large class of graphs that includes all bipartite graphs as well as many graphs of high girth and high chromatic number. [ABSTRACT FROM AUTHOR]

Abstract: Correspondence coloring, or DP‐coloring, is a generalization of list coloring introduced recently by Dvořák and Postle [11]. In this article, we establish a version of Dirac's theorem on the minimum number of edges in critical graphs [9] in the framework of DP‐colorings. A corollary of our main result answers a question posed by Kostochka and Stiebitz [15] on classifying list‐critical graphs that satisfy Dirac's bound with equality. [ABSTRACT FROM AUTHOR]

A graph G is - colorable if can be partitioned into two sets and so that the maximum degree of is at most j and of is at most k. While the problem of verifying whether a graph is (0, 0)-colorable is easy, the similar problem with in place of (0, 0) is NP-complete for all nonnegative j and k with . Let denote the supremum of all x such that for some constant every graph G with girth g and for every is -colorable. It was proved recently that . In a companion paper, we find the exact value . In this article, we show that increasing g from 5 further on does not increase much. Our constructions show that for every g, . We also find exact values of for all g and all . [ABSTRACT FROM AUTHOR]

For a hypergraph G and a positive integer s, let [ABSTRACT FROM AUTHOR]

Two n-vertex hypergraphs G and H pack, if there is a bijection [ABSTRACT FROM AUTHOR]