Sum-list-colouring of θ-hypergraphs

Ewa Drgas-Burchardt, Agata Drzystek, Elżbieta Sidorowicz


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.


Hypergraphs, sum-list-colouring, θ-hypergraphs

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications