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]

A graph G is d‐degenerate if every nonnull subgraph of G has a vertex of degree at most d. We prove that every n‐vertex planar graph has a 3‐degenerate induced subgraph of order at least 3n∕4. [ABSTRACT FROM AUTHOR]

We take an application of the Kernel Lemma by Kostochka and Yancey [11] to its logical conclusion. The consequence is a sort of magical way to draw conclusions about list coloring (and online list coloring) just from the existence of an independent set incident to many edges. We use this to prove an Ore-degree version of Brooks' Theorem for online list-coloring. The Ore-degree of an edge [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]

For k ∈ N, Corrádi and Hajnal proved that every graph G on 3k vertices with minimum degree δ (G)≥ 2k has a C 3 -factor, i.e., a partitioning of the vertex set so that each part induces the 3-cycle C 3. Wang proved that every directed graph G ⃗ on 3k vertices with minimum total degree δ t (G ⃗)≔minv ∈V (d e g −(v)+d e g +(v))≥ 3(3k − 1)/ 2 has a C ⃗ 3 -factor, where C ⃗ 3 is the directed 3-cycle. The degree bound in Wang's result is tight. However, our main result implies that for all integers a ≥ 1 and b ≥ 0 with a +b =k, every directed graph G ⃗ on 3k vertices with minimum total degree δ t (G ⃗)≥ 4k − 1 has a factor consisting of a copies of T ⃗ 3 and b copies of C ⃗ 3, where T ⃗ 3 is the transitive tournament on three vertices. In particular, using b = 0, there is a T ⃗ 3 -factor of G ⃗, and using a = 1, it is possible to obtain a C ⃗ 3 -factor of G ⃗ by reversing just one edge of G ⃗. All these results are phrased and proved more generally in terms of undirected multigraphs. We conjecture that every directed graph G ⃗ on 3k vertices with minimum semidegree δ 0(G ⃗)≔minv ∈V min(d e g −(v),d e g +(v))≥ 2k has a C ⃗ 3 -factor, and prove that this is asymptotically correct. [ABSTRACT FROM AUTHOR]

A graph G is equitably k-choosable if for every k-list assignment L there exists an L-coloring of G such that every color class has at most [ABSTRACT FROM AUTHOR]

Chen et al., conjectured that for r≥3, the only connected graphs with maximum degree at most r that are not equitably r-colorable are K r, r (for odd r) and K r + 1. If true, this would be a joint strengthening of the Hajnal-Szemerédi theorem and Brooks' theorem. Chen et al., proved that their conjecture holds for r = 3. In this article we study properties of the hypothetical minimum counter-examples to this conjecture and the structure of 'optimal' colorings of such graphs. Using these properties and structure, we show that the Chen-Lih-Wu Conjecture holds for r≤4. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:31-48, 2012 [ABSTRACT FROM AUTHOR]

A class Γ of graphs is χ-bounded if there eχists a function f such that χ (G) ⩽ f (&oωega; (G)) for all graphs G ϵ Γ, ωhere χ denotes chromatic number and ω denotes clique number. Gyárfás and Sumner independently conjectured that, for any tree T, the class Forb (T), consisting of graphs that do not contain T as an induced subgraph, is χ-bounded. The first author and Penrice showed that this conjecture is true for any radius two tree. Here we use the work of several authors to show that the conjecture is true for radius three trees obtained from radius two trees by making exactly one subdivision in every edge adjacent to the root. These are the only trees with radius greater than two, other than subdivided stars, for which the conjecture is known to be true. [ABSTRACT FROM AUTHOR]

Previously, Erdős, Kierstead and Trotter [5] investigated the dimension of random height 2 partially ordered sets. Their research was motivated primarily by two goals: (1) analyzing the relative tightness of the Füredi–Kahn upper bounds on dimension in terms of maximum degree; and (2) developing machinery for estimating the expected dimension of a random labeled poset on n points. For these reasons, most of their effort was focused on the case 0 < p ≤ 1 / 2 . While bounds were given for the range 1 / 2 ≤ p < 1 , the relative accuracy of the results in the original paper deteriorated as p approaches 1. Motivated by two extremal problems involving conditions that force a poset to contain a large standard example, we were compelled to revisit this subject, but now with primary emphasis on the range 1 / 2 ≤ p < 1 . Our sharpened analysis shows that as p approaches 1, the expected value of dimension increases and then decreases, answering in the negative a question posed in the original paper. Along the way, we apply inequalities of Talagrand and Janson, establish connections with latin rectangles and the Euler product function, and make progress on both extremal problems. [ABSTRACT FROM AUTHOR]

Let G and H be balanced U, V -bigraphs on 2n vertices with Δ(H) ⩽ 2. Let k be the number of components of H, δU := min(degG(u) : u ϵ U) and δV := min(degG(v) : v ϵ V ). We prove that if n is sufficiently large and ϵU +ϵV ⩾ n+k, then G contains H. This answers a question of Amar in the case that n is large. We also show that G contains H even when ϵU + ϵV ⩾ n+2 as long as n is sufficiently large in terms of k and ϵ(G) ⩾ n/200k + 1. [ABSTRACT FROM AUTHOR]