Sum-List Colouring of Unions of a Hypercycle and a Path with at Most Two Vertices in Common

Abstract

Given a hypergraph 𝒣 and a function f : V (𝒣) → 𝕅, we say that 𝒣 is f-choosable if there is a proper vertex colouring ϕ of 𝒣 such that ϕ (v) ∈ L(v) for all v ∈ V (𝒣), where L : V (𝒣) → 2𝕅 is any assignment of f(v) colours to a vertex v. The sum choice number 𝒣isc(𝒣) of 𝒣 is defined to be the minimum of Σv∈V(𝒣)f(v) over all functions f such that 𝒣 is f-choosable. For an arbitrary hypergraph 𝒣 the inequality χsc(𝒣) ≤ |V (𝒣)| + |ɛ (𝒣)| holds, and hypergraphs that attain this upper bound are called sc-greedy. In this paper we characterize sc-greedy hypergraphs that are unions of a hypercycle and a hyperpath having at most two vertices in common. Consequently, we characterize the hypergraphs of this type that are forbidden for the class of sc-greedy hypergraphs.

Keywords

• hypergraphs
• sum-list colouring
• induced hereditary classes
• forbidden hypergraphs
• 05c15
• 05c65