Sum-list-colouring of θ-hypergraphs

Abstract

Given a hypergraph ℋ and a function f: V(ℋ) → ℕ, we say that ℋ is f-choosable if there is a proper vertex coloring ϕ of ℋ such that ϕ(v) ∈ L(v) for all v ∈ V(ℋ), where L: V(ℋ) → 2^ℕ is any assignment of f(v) colors to a vertex v. The sum choice number χ_sc(ℋ) of ℋ is defined to be the minimum of ∑_{v ∈ V(ℋ)}f(v) over all functions f such that ℋ is f-choosable. A trivial upper bound on χ_sc(ℋ) is |V(ℋ)| + |ℰ(ℋ)|. The class Γ_sc of hypergraphs that achieve this bound is induced hereditary. We analyze some properties of hypergraphs in Γ_sc as well as properties of hypergraphs in the class of forbidden hypergraphs for Γ_sc. We characterize all θ-hypergraphs in Γ_sc, which leads to the characterization of all θ-hypergraphs that are forbidden for Γ_sc.