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.
Keywords
DOI: https://doi.org/10.26493/1855-3974.2083.e80
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