A Hypergraph Version of a Graph Packing Theorem by Bollobás and Eldridge

Two n‐vertex hypergraphs G and H pack, if there is a bijection such that for every edge , the set is not an edge in H. Extending a theorem by Bollobás and Eldridge on graph packing to hypergraphs, we show that if and n‐vertex hypergraphs G and H with with no edges of size 0, 1, and n do not pack, then either

1. one of G and H contains a spanning graph‐star, and each vertex of the other is contained in a graph edge, or
2. one of G and H has edges of size not containing a given vertex, and for every vertex x of the other hypergraph some edge of size does not contain x.

     

Equitable List Coloring of Graphs with Bounded Degree

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 vertices. We prove results toward the conjecture that every graph with maximum degree at most r is equitably ‐choosable. In particular, we confirm the conjecture for and show that every graph with maximum degree at most r and at least r³ vertices is equitably ‐choosable. Our proofs yield polynomial algorithms for corresponding equitable list colorings.     

The Dimension of Neighboring Levels of the Boolean Lattice

The order dimension of suborders of the Boolean lattice is considered. It is shown that the suborder of consisting of levels s and s+1 has dimension O(\log n/log log n). This improves a bound in [1].     

Acyclic list 7‐coloring of planar graphs

The acyclic list chromatic number of every planar graph is proved to be at most 7. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 83–90, 2002     

A class of constructions for turán’s (3, 4)-problem

Letf(n) denote the minimal number of edges of a 3-uniform hypergraphG=(V, E) onn vertices such that for every quadrupleY ⊂V there existsY ⊃e ∈E. Turán conjectured thatf(3k)=k(k−1)(2k−1). We prove that if Turán’s conjecture is correct then there exist at least 2 ^k−2 non-isomorphic extremal hypergraphs on 3k vertices.     

Ore’s conjecture for k=4 and Grötzsch’s Theorem

A graph G is k-critical if it has chromatic number k, but every proper subgraph of G is (k?1)-colorable. Let f _k (n) denote the minimum number of edges in an n-vertex k-critical graph. In a very recent paper, we gave a lower bound, f _k (n)≥(k, n), that is sharp for every n≡1 (mod k?1). It is also sharp for k=4 and every n≥6. In this note, we present a simple proof of the bound for k=4. It implies the case k=4 of two conjectures: Gallai in 1963 conjectured that if n≡1 (mod k?1) then \(f_k (n)\tfrac{{(k + 1)(k - 2)n - k(k - 3)}} {{2(k - 1)}}\) , and Ore in 1967 conjectured that for every k≥4 and \(n \geqslant k + 2,f_k (n + k - 1) = f(n) + \tfrac{{k - 1}} {2}(k - \tfrac{2} {{k - 1}})\) . We also show that our result implies a simple short proof of Grötzsch’s Theorem that every triangle-free planar graph is 3-colorable.