ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P1.05 / 83–97
https://doi.org/10.26493/1855-3974.2083.e80
(Also available at http://amc-journal.eu)
Sum-list-colouring of θ-hypergraphs
Ewa Drgas-Burchardt * , Agata Drzystek, Elżbieta Sidorowicz
Faculty of Mathematics, Computer Science and Econometrics,
University of Zielona Góra, Prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland
Received 12 August 2019, accepted 10 May 2021, published online 21 February 2022
Abstract
Given a hypergraph H and a function f : V (H) → N, we say that H is f -choosable
if there is a proper vertex coloring ϕ of H such that ϕ(v) ∈ L(v) for all v ∈ V (H),
where L : V (H) → 2N is any assignment of f(v) colors to a vertex v. The sum choice
number χsc(H) of H is defined to be the minimum of
∑
v∈V (H) f(v) over all functions
f such that H is f -choosable. A trivial upper bound on χsc(H) is |V (H)| + |E(H)|.
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: Hypergraphs, sum-list-colouring, θ-hypergraphs.
Math. Subj. Class. (2020): 05C15, 05C65
1 Introduction
A hypergraph is a very natural generalization of a graph. It always motivates the exten-
sion of a problem first posed in the class of graphs to the class of hypergraphs. If it is
a vertex colouring problem, then there is additional motivation. Indeed, a lot of scientists
consider different concepts of vertex colouring of graphs (for example: list-colouring, sum-
colouring, equitable-colouring), starting, in each case, from proper colouring, and next,
analyzing some improper variants, in which a graph induced by vertices of a colour class
is not necessarily edgeless. If we assume that each colour class has to induce a graph with
some property (for example: acyclic, with a bounded degree, and so on) and this property
is closed with respect to induced subgraphs, then, in each of these concepts, the problem of
improper colouring of a graph is equivalent to the problem of proper colouring of a unique
*Corresponding author.
E-mail addresses: e.drgas-burchardt@wmie.uz.zgora.pl (Ewa Drgas-Burchardt),
a.drzystek@wmie.uz.zgora.pl (Agata Drzystek), e.sidorowicz@wmie.uz.zgora.pl (Elżbieta Sidorowicz)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
84 Ars Math. Contemp. 22 (2022) #P1.05 / 83–97
hypergraph constructed for this graph. Clearly, the construction of such a hypergraph can
be difficult, but this approach gives the possibility to solve the problem. Moreover, in this
case, each of the results obtained for hypergraphs can be applied to different variants of the
same concept of graph colouring. Consequently, it can produce many special results.
The concept of sum-list-colouring of graphs is motivated by real problems and was first
introduced in [6, 8]. Erdős, Rubin and Taylor [6] considered the so called size functions
whose values for vertices of a graph represented the sizes of the lists assigned to them.
Isaak [8] was the first to analyze the minimum sum of the list sizes that guarantees the
existence of any particular proper vertex list colouring if lists are of these sizes. Such an
invariant was determined in [11], with the help of Hall’s Theorem, for complete graphs,
and then, for a few other classes of graphs [9, 12]. In [9] the upper bound on the minimum
sum of the list sizes was determined. Graphs that meet this bound, known as sc-greedy,
led themselves to a very popular line of investigation in the literature [2, 3, 7, 9, 12]. In
[5], the authors analyzed sum-list-colouring concept assuming that colour classes need
not be edgeless. This investigation shows some differences between proper and improper
cases and uses hypergraph theory tools. We continue this consideration herein, focusing
on hypergraphs, believing that the following results will be used for various variants of
the colouring concept. We extend the sc-greedy notion from graphs to hypergraphs and
characterize all θ-hypergraphs that are sc-greedy (Theorem 4.11). This yields the charac-
terization of all θ-hypergraphs that are forbidden for the class of sc-greedy hypergraphs
(Corollary 4.12).
2 Preliminaries
In general, we follow the notation and terminology of [1, 4]. A hypergraph H consists of a
non-empty finite set V (H) of vertices and a finite set E(H) of at least 2-element subsets of
V (H), called edges. A hypergraph is simple if none of its edges is a subset of another edge.
A hypergraph is linear if any two of its edges have no more than one vertex in common.
Let H be a hypergraph. A hypergraph H′ is a subhypergraph of H if V (H′) ⊆ V (H)
and E(H′) ⊆ E(H). For V ′ ⊆ V (H), a subhypergraph of a hypergraph H induced by V ′,
denoted by H[V ′], has the vertex set V ′ and the edge set {E ∈ E(H) : E ⊆ V ′}. We use
H− V ′ notation instead of H[V (H) \ V ′] and even H− v instead of H− {v}.
Let H be a hypergraph, v ∈ V (H) and E(v) = {E ∈ E(H) : v ∈ E}. By H(v) we
denote a hypergraph with the vertex set ∪E∈E(v)E and with the edge set E(v). The degree
of v in H, denoted by degH(v), is defined as the number of edges of H(v). The β-degree
of v in H, denoted by degβH(v), is the largest number of edges of a linear subhypergraph
of H(v). The H1 ∪ H2 symbol denotes the union of disjoint hypergraphs H1, H2. By the
identification of two non-adjacent vertices v1 and v2 (in a hypergraph H into a vertex w)
we mean the result of the following operations on H: the removal of vertices v1, v2, the
addition of a new vertex w, the replacement of each edge containing either v1 or v2 by an
edge in which w substitutes v1, v2, respectively, and the removal of multiple edges if the
current hypergraph has such edges. Note that v1, v2 can be vertices of different compo-
nents, say H1,H2, of H. In this case, sometimes, instead of the identification of vertices
in H1 ∪ H2 we may talk about the identification of vertices of two disjoint hypergraphs
H1,H2.
The 1-vertex hypergraph is a hypertree without edges. Next, a hypergraph that has one
edge consisting of all its vertices is a hypertree with one edge. A hypertree with m edges
E. Drgas-Burchardt et al.: Sum-list-colouring of θ-hypergraphs 85
(m ≥ 2) can be constructed from a hypertree H1 with m1 edges and a hypertree H2 with
m − m1 edges, 0 < m1 < m, by the identification of an arbitrary vertex of H1 and an
arbitrary vertex of H2. Note that each hypertree is linear.
A hypertree H is a hyperpath if there is an ordering (called canonical) of V (H) such
that each edge of H consists of some consecutive vertices (with respect to this ordering).
The length of a hyperpath is the number of its edges. By a hypercycle we mean a hypergraph
obtained from a hyperpath of length of at least three by the identification of the vertex with
the first index and the vertex with the last index in an arbitrary canonical ordering of the
vertex set of this hyperpath. The length of a hypercycle is the same as the length of a
hyperpath that was used in the construction. Moreover, if v1, . . . , vn is a canonical ordering
of the vertex set of the hyperpath, then v1, . . . , vn−1 is a canonical ordering of the vertex set
of the resulting hypercycle. Let k ∈ N. By a k-edge, k+-edge (of a hypergraph H) we mean
an edge of H consisting of k, at least k vertices, respectively. A hypergraph is k-uniform
if each of its edges is a k-edge. Thus 2-uniform hypergraphs are graphs and especially,
2-uniform hypertrees, hyperpaths, hypercycles are trees, paths, cycles, respectively.
3 Sum-choice-number of hypergraphs
Let H be a hypergraph. A proper colouring of H is a mapping ϕ : V (H) → N such
that for every edge E of H there are at least two different vertices v1, v2 in E such that
ϕ(v1) ̸= ϕ(v2). Given a mapping L : V (H) → 2N we call a mapping ϕ : V (H) → N an
L-colouring of H if for every vertex v ∈ V (H) it holds that ϕ(v) ∈ L(v). Let f be a
function from V (H) to the set of positive integers, a mapping L : V (H) → 2N such that
|L(v)| = f(v) for every vertex v in V (H) is called an f -assignment for H. The hypergraph
H is f -choosable if for each f -assignment L for H there is a proper L-coloring of H. Thus,
H is f -choosable if H is properly L-colourable for each f -assignment L for H. The sum-
choice-number χsc(H) of H is defined as the minimum of
∑
v∈V (H) f(v) taken over all f
such that H is f -choosable. Hence
χsc(H) = minf
 ∑
v∈V (H)
f(v) : H is f -choosable
 .
If H is f -choosable and χsc(H) =
∑
v∈V (H) f(v), then we say that f realizes χsc(H).
The definition of the sum-choice-number of a hypergraph implies some immediate ob-
servations.
Fact 3.1. If a hypergraph H1 is f -choosable for some function f with a domain V (H1),
then each subhypergraph H2 of H1 is f |V (H2)-choosable.
Fact 3.2. If H1,H2 are vertex disjoint hypergraphs, then
χsc(H1 ∪H2) = χsc(H1) + χsc(H2).
Fact 3.3. If H2 is a subhypergraph of a hypergraph H1, then
|V (H1)| − |V (H2)|+ χsc(H2) ≤ χsc(H1).
Applying the reasoning provided in the proof of Theorem 8 from [5] we obtain the
following theorem.
86 Ars Math. Contemp. 22 (2022) #P1.05 / 83–97
Theorem 3.4. If H is a hypergraph and v1, . . . , vn is an arbitrary ordering of V (H), then
χsc(H) ≤
n∑
i=1
degβHi(vi) + n,
where Hi = H[{v1, . . . , vi}].
Proof. Given the ordering v1, . . . , vn, let f(vi) = deg
β
Hi(vi) + 1. To finish the proof we
will show that H is f -choosable. Let L be any f -assignment for H. We colour the vertices
of H greedily, in accordance with the ordering v1, . . . , vn. Namely, in the ith step we assign
to vi the least colour from L(vi) such that for each a ∈ N the hypergraph induced by the
vertices coloured with a in the hypergraph Hi is edgeless. Note that such a colouring exists
for each of ith steps, i ∈ {1, . . . , n}, since, there are at most degβHi (vi) colours in L(vi)
for which Hi has an edge that would be monochromatic if we assigne this colour to vi.
Using the reasoning presented in the final part of the above proof we have the following
property.
Lemma 3.5. If H is a hypergraph and f is a function that realizes χsc(H), then f(v) ≤
degβH(v) + 1 for each v ∈ V (H).
Proof. Suppose, for contradiction purposes, that f satisfies the assumptions of the lemma
and there is a vertex u ∈ H such that f(u) ≥ degH(u) + 2. We will show that H is f ′-
choosable for f ′ defined by f ′(v) = f(v) for v ∈ V (H)\{u} and f ′(u) = f(u)−1, giving
a contradiction with the assumptions about f . Let H′ = H−u and let f ′-assignment L′ for
H be given. Since f ′|V (H′) = f |V (H′) we know that there is a proper L′|V (H′)-colouring
ϕ′ of H′, by Fact 3.1. Clearly ϕ′ can be extended to a proper L′-colouring of H since
f ′(u) ≥ degβH(u) + 1.
Observe that the bound given in Theorem 3.4 mostly depends on the ordering of ver-
tices. For example, consider a hypergraph H such that V (H) = {v1, . . . , v5} and E(H) =
{E1, E2, E3}, where E1 = {v1, v2, v3, v4}, E2 = {v1, v2, v3, v5} and E3 = {v1, v2, v4,
v5}. Let π1 : v1, v2, v3, v4, v5 and π2 : v3, v4, v5, v1, v2 be two different orderings of V (H).
Thus Theorem 3.4 gives the upper bound of 7 on χsc(H) when we use π1 and of 6 when
we use π2. On the other hand deg
β
H(v) ≤ degH(v) for every vertex v of a hypergraph H.
Moreover, for any ordering v1, . . . , vn of vertices of an n-vertex hypergraph H we have∑n
i=1 degHi(vi) = |E(H)|, where Hi = H[{v1, . . . , vi}]. Hence Theorem 3.4 implies the
following fact.
Fact 3.6. If H is a hypergraph, then
χsc(H) ≤ |V (H)|+ |E(H)|.
A hypergraph H is called sc-greedy if χsc(H) = |V (H)| + |E(H)|. In brief, in the
following, we denote the number |V (H)|+|E(H)| by GB(H). The notion of sc-greediness
was previously introduced for graphs in [2]. Observe that if H is an sc-greedy hypergraph,
then for every ordering v1, . . . , vn of V (H) it holds that degβHi(vi) = degHi(vi) for each
permissible i and Hi = H[{v1, . . . , vi}]. Now suppose that a hypergraph has at least two
edges E1, E2 that have at least two vertices, in common, say {v1, v2} ⊆ E1 ∩ E2. We
construct an ordering of vertices of H putting first the vertices from E1 \ {v1, v2}, next
E. Drgas-Burchardt et al.: Sum-list-colouring of θ-hypergraphs 87
the vertices from E2 \ {v1, v2}, next v1, v2, and finally the remaining vertices. Clearly,
degβHj (v2) < degHj (v2), where j = |E1 ∪ E2|. Hence we conclude the following fact.
Fact 3.7. Each sc-greedy hypergraph is linear.
The literature on sc-greediness of graphs is very rich. We try to comment this property
in the class of hypergraphs, especially those hypergraphs that are not graphs. Let Γsc
denote the family of all sc-greedy hypergraphs. First note that Γsc is not closed while
taking subhypergraphs. Indeed, the K2,3 graph is not sc-greedy, but a graph resulting from
K2,3 by the addition of an edge, which joins two vertices of degree 3, is sc-greedy [12].
On the other hand, Γsc is closed while taking induced subhypergraphs (it is a well-known
fact for sc-greedy graphs). To see it, suppose that there is an sc-greedy hypergraph H
having an induced subhypergraph H′, which is not sc-greedy. We construct a function f
such that H is f -choosable and
∑
v∈V (H) f(v) ≤ GB(H) − 1 based on the function f ′
that realizes χsc(H′). Actually, f |V (H′) = f ′ and for i ∈ {1, . . . , p} we put f(vi) =
degβHi(vi) + 1, where v1, . . . , vp is an arbitrary ordering of V (H) \ V (H
′) and Hi =
H[V (H′)∪{v1, . . . , vi}]. It implies that H is not sc-greedy, contradicting our assumption.
Thus Γsc is an induced hereditary class and there is a family C(Γsc) of hypergraphs, each
of which is not sc-greedy and whose each proper induced subhypergraph is sc-greedy. The
elements of C(Γsc) are called forbidden hypergraphs for Γsc and they uniquely determine
Γsc. Note that Γsc contains only linear hypergraphs. The class C(Γsc) does not have
this property. For example, each non-linear hypergraph H defined by V (H) = E1 ∪ E2,
E(H) = {E1, E2}, where |E1 ∩ E2| ≥ 2, E1 \ E2 ̸= ∅, E2 \ E1 ̸= ∅, is an element
of C(Γsc).
In the next part of the paper we focus our attention on linear hypergraphs in C(Γsc).
Lemma 3.8. Let H be a linear hypergraph in C(Γsc) and v ∈ V (H). If f is a function
that realizes χsc(H), then
i) f(v) ≤ degH(v), and
ii) degH(v) ≥ 2 implies f(v) ≥ 2 provided that each edge in E(H(v)) contains in H
at most two vertices of degree greater than one.
Proof. To show i) suppose that there is at least one vertex u in V (H) such that f(u) ≥
degH(u) + 1. Lemma 3.5 says that f(u) = degH(u) + 1. Now we define H′ = H − u.
Clearly H′ is a proper induced subhypergraph of H and consequently is sc-greedy, by the
definition of C(Γsc). From the construction we know that |V (H′)| = |V (H)| − 1 and
|E(H′)| = |E(H)| − degH(u). Thus χsc(H′) = GB(H′) = GB(H) − (degH(u) + 1).
As a subhypergraph of H, the hypergraph H′ is f |V (H′)-choosable, by Fact 3.1. It follows
that χsc(H′) ≤
∑
v∈V (H′) f(v) =
∑
v∈V (H) f(v) − (degH(u) + 1) ≤ GB(H) − 1 −
(degH(u)+1). Thus GB(H)−1−(degH(u)+1) ≥ χsc(H′) = GB(H)−(degH(u)+1),
i.e. a contradiction.
To show ii) suppose that H and u ∈ V (H) satisfy the assumptions and f(u) = 1. If
there is an edge E ∈ E(H(u)) that contains only one vertex of degree greater than one
(only u), then for each vertex in E the value of f is equal to one, and consequently H is not
f -choosable, a contradiction. Let {E1, . . . , Ek} = E(H(u)). Thus for each i ∈ {1, . . . , k}
there is exactly one vertex ui different from u such that ui ∈ Ei and degH(ui) ≥ 2. Let
H′ = H[(V (H)\∪ki=1Ei)∪{u1, . . . , uk}]. Note that |E(H′)| = |E(H)|−k and |V (H′)| =
88 Ars Math. Contemp. 22 (2022) #P1.05 / 83–97
|V (H)| − t for some t ∈ N. We define f ′ : V (H′) → N such that f ′(v) = f(v) if
v /∈ {u1, . . . , uk} and f ′(ui) = f(ui)−1 for i ∈ {1, . . . , k}. Note that
∑
v∈V (H′) f
′(v) ≤∑
v∈V (H) f(v) − k − t. Since H ∈ C(Γsc), it holds that
∑
v∈V (H) f(v) ≤ GB(H) − 1,
and consequently
∑
v∈V (H′) f
′(v) ≤ GB(H) − 1 − k − t = GB(H′) − 1. Thus H′
is not f ′-choosable. Let L′ be an f ′-assignment for H′ such that there is no proper L′-
colouring of H′ and let a /∈
⋃
v∈V (H′) L
′(v). We define an f -assignment L for H in the
following way: L(v) = L′(v) for v ∈ V (H′) \ {u1, . . . , uk}, next L(ui) = L′(ui) ∪ {a}
for i ∈ {1, . . . , k} and L(v) = {a} for v ∈ V (H) \ V (H′). It is very easy to see that there
is no proper L-colouring of H, which means that H is not f -choosable contradicting the
assumption. Hence f(u) ≥ 2 in this case.
Let us continue the investigation concerning sc-greedy hypergraphs. We start with the
observation that Theorem 1 in [2] (referring to graphs) can be extended to hypergraphs. In
fact, the same proof, in which the words graphs are substituted by hypergraphs, works to
obtain the following statement.
Theorem 3.9. Let H1, H2 be two disjoint hypergraphs and v1 ∈ V (H1), v2 ∈ V (H2). If
H is the hypergraph obtained by the identification of v1 and v2 in H1 ∪H2, then
χsc(H) = χsc(H1) + χsc(H2)− 1.
Note that each hypertree with one edge is sc-greedy. The recursion used in the defini-
tion of a hypertree with an arbitrary number of edges and Theorem 3.9 give us the following
consequence.
Corollary 3.10. Each hypertree is sc-greedy.
Using Lemma 3.8 concerning hypergraphs in C(Γsc), we have the next result.
Theorem 3.11. Each hypercycle is sc-greedy.
Proof. Clearly, if there is a hypercycle H that is not sc-greedy, then H ∈ C(Γsc). It follows
by Corollary 3.10 and Fact 3.2, since each component of every proper induced subhyper-
graph of H is a hypertree (actually it is a hyperpath). Suppose that f realizes χsc(H).
By Lemma 3.8 i), ii) we have f(v) ≥ degH(v) for each vertex of H, and consequently∑
v∈H f(v) ≥ GB(H), a contradiction.
Let F be the class of recursively defined hypergraphs such that: all hypercycles and all
hypertrees are in F , and, giving any two disjoint hypergraphs H1, H2 in F and vertices
v1 ∈ V (H1), v2 ∈ V (H2), a hypergraph obtained by the identification of v1 and v2 in
H1 ∪H2 is also in F .
The following result is a consequence of Corollary 3.10 and Theorems 3.11, 3.9.
Corollary 3.12. If H ∈ F , then H is sc-greedy.
4 θ-hypergraphs
Let k1, k2, k3 ∈ N. By θhk1,k2,k3 we denote the hypergraph consisting of two vertices of
degree 3 connected by three internally disjoint hyperpaths of lengths k1, k2, k3. In what
follows, we sometimes use the notion of a hyperpath of θhk1,k2,k3 of length ki, i ∈ {1, 2, 3},
E. Drgas-Burchardt et al.: Sum-list-colouring of θ-hypergraphs 89
meaning the hyperpath of length ki, used in the definition of θhk1,k2,k3 . By a θ-hypergraph
we mean an arbitrary hypergraph θhk1,k2,k3 . Observe that if at least two of the numbers
k1, k2, k3 are equal to one, then θhk1,k2,k3 is not linear. Additionally, if one of the hyperpaths
of length one is created by a 2-edge, θhk1,k2,k3 is even not simple. When θ
h
k1,k2,k3
is a graph,
we can denote it by θk1,k2,k3 since such notation is present in the literature. In [7] Heinold
found the values χsc(θk1,k2,k3) for all simple graphs θk1,k2,k3 . We recall here this result.
Theorem 4.1 ([7]). Let k1, k2, k3 ∈ N and at most one of k1, k2, k3 is equal to one. A
graph θk1,k2,k3 is not sc-greedy if and only if k1 = k2 = 2 and k3 is even. Moreover, if
θk1,k2,k3 is not sc-greedy, then
χsc(θk1,k2,k3) = GB(θk1,k2,k3)− 1.
Theorem 4.1 shows that the sum-choice-number of each simple graph θk1,k2,k3 , is al-
ways less by one or equal to the sum of the numbers of vertices and edges of this graph.
Fortunately, θ-hypergraphs have the same property.
Lemma 4.2. If k1, k2, k3 ∈ N and at most two of the numbers k1, k2, k3 are equal to one,
then χsc(θhk1,k2,k3) ≥ GB(θ
h
k1,k2,k3
)− 1.
Proof. Let H = θhk1,k2,k3 and let E be an arbitrary edge of H that is one of the edges of the
shortest hyperpath among three hyperpaths that compose H. Next let H′ be a subhyper-
graph of H such that V (H′) = V (H) and E(H′) = E(H)\{E}. Note that H′ is sc-greedy,
by Corollary 3.12 and Fact 3.2. It means χsc(H′) ≥ GB(θhk1,k2,k3)−1. Thus the statement
follows from Fact 3.3.
It is worth mentioning that χsc(θh1,1,1) = GB(θ
h
1,1,1) − 2. Indeed, let v be one of two
vertices of degree 3 in V (θh1,1,1) and let f : V (θ
h
1,1,1) → N be defined by: f(v) = 2 and
f(u) = 1 for every u ∈ V (θh1,1,1) \ {v}. Clearly, θh1,1,1 is f -choosable since, for every
f -assignment L, each colouring, in which the colours of v and the other vertex of degree
3 are different, is a proper L-colouring of θh1,1,1. Thus, χsc(θ
h
1,1,1) ≤ GB(θh1,1,1) − 2 =
|V (θh1,1,1)|+ 1. Because θh1,1,1 has edges, we have χsc(θh1,1,1) ≥ |V (θh1,1,1)|+ 1.
Let f : V (H) → N and L be an f -assignment for H. In what follows, if L(v) =
{a1, . . . , af(v)}, then we always assume that elements a1, . . . , af(v) are pairwise different.
Thus, among others, in Lemma 4.3 the integers a, b, c are pairwise different. Furthermore,
if i1, . . . , ip are consecutive integers and i1 > ip, then the set {i1, . . . , ip} is empty.
Lemma 4.3. Let k ∈ N and H be a hypercycle of length 2k. Next let v1, . . . , vn be an
arbitrary canonical ordering of V (H), where {vi1 = v1, . . . , vi2k} is the set of all vertices
of degree two in H with ij < il for j < l.
If f : V (H) → N is defined by f(v) = degH(v) and L is an f -assignment for H such
that
i) L(vij ) = {a, b} for j ∈ {1, . . . , 2k − 2}, and
ii) L(vi2k−1) = {b, c}, and
iii) L(vi2k) = {a, c}, and
iv) L(vs) = {c} for s ∈ {i2k−1 + 1, . . . , i2k − 1}, and
90 Ars Math. Contemp. 22 (2022) #P1.05 / 83–97
v) L(vs) = {a} for s ∈ {i2k + 1, . . . , n} or for s ∈ {ir + 1, . . . , ir+1 − 1} with odd r,
1 ≤ r ≤ 2k − 3, and
vi) L(vs) = {b} for s ∈ {ir + 1, . . . ir+1 − 1} with even r, 2 ≤ r ≤ 2k − 2,
then in each proper L-colouring ϕ of H it holds that ϕ(v1) = b.
Proof. Suppose that there is a proper L-colouring ϕ of H such that ϕ(v1) = a. Con-
sequently, it must be ϕ(vi2p) = b for all p ∈ {1, . . . , k − 1}, next ϕ(vi2k−1) = c and
ϕ(vi2k) = a. Hence the edge {vi2k , . . . , vn, v1} is monochromatic in ϕ, a contradic-
tion.
To avoid repetitions, we skip the simple proof of the next lemma that can be done in
the same manner as the proof of Lemma 4.3.
Lemma 4.4. Let k ∈ N and H be a hypercycle of length 2k + 1. Next let v1, . . . , vn be
an arbitrary canonical ordering of V (H), where {vi1 = v1, . . . , vi2k+1} is the set of all
vertices of degree two in H with ij < ik for j < k.
If f : V (H) → N is defined by f(v) = degH(v) and L is an f -assignment for H such
that
i) L(vij ) = {a, b} for j ∈ {1, . . . , 2k + 1}, and
ii) L(vs) = {a} for s ∈ {i2k+1 + 1, . . . , n} or for s ∈ {ir + 1, . . . , ir+1 − 1} with odd
r, 1 ≤ r ≤ 2k − 1, and
iii) L(vs) = {b} for s ∈ {ir + 1, . . . ir+1 − 1} and even r, 2 ≤ r ≤ 2k,
then in each proper L-colouring ϕ of H it holds that ϕ(v1) = b.
Lemma 4.5. Let k1, k2, k3 ∈ N. If the hyperpath of length k2 of θhk1,k2,k3 has only 2-edges,
and either
i) k1 + k2 and k2 + k3 are odd numbers and at least one of the inequalities k1 ≥ 2,
k3 ≥ 2 holds, or
ii) k1 + k2 is an odd number and k2 + k3 is an even number and k3 ≥ 3, or
iii) k1 + k2 is an even number and k2 + k3 is an even number and k1 ≥ 3 and k3 ≥ 3,
then θhk1,k2,k3 is sc-greedy.
Proof. Let H = θhk1,k2,k3 and let H satisfies the assumptions of the lemma. Observe that
at most one of integers k1, k2, k3 is equal to one since otherwise, H does not satisfy the
assumptions of the lemma, so H is linear.
Suppose, for a contradiction, that H is not sc-greedy. Since each component of each
proper induced subhypergraph of H is in F , we obtain H ∈ C(Γsc), by Corollary 3.12 and
Fact 3.2. Let f be a function that realizes χsc(H). Lemma 3.8 i) implies that f(v) = 1 if
degH(v) = 1 and Lemma 3.8 ii) implies that f(v) ≥ 2 for each vertex v of degree greater
than one. Thus f has values in {1, 2} and is fixed, since
∑
v∈V (H) f(v) = GB(H) − 1
(see Lemma 4.2).
Now we shall construct an f -assignment L for H such that H is not properly L-
colourable. Assume that P1,P2,P3 are three hyperpaths of lengths k1, k2, k3, respectively,
E. Drgas-Burchardt et al.: Sum-list-colouring of θ-hypergraphs 91
from which θhk1,k2,k3 is composed. Next let C1 be a hypercycle that is a subhypergraph of
θhk1,k2,k3 composed from vertices and edges of the hyperpaths P1,P2. Similarly, let C2 be
a hypercycle that is a subhypergraph of θhk1,k2,k3 composed from vertices and edges of the
hyperpaths P2,P3. Thus lengths of C1, C2 are k1 + k2 and k2 + k3, respectively. Now we
define canonical orderings π1 of C1 and π2 of C2, both starting with the same fixed vertex
of degree three in H, say v1, and both proceeding consecutively, first along the vertices of
P2, and next, along the vertices of either P1 or P3, respectively.
Next we construct an f -assignment L1 for C1 and π1 either in accordance with Lem-
ma 4.3 or in accordance with Lemma 4.4, depending on the parity of the length of C1 (the
parity of k1 + k2). Similarly, we construct an f -assignment L2 for C2 and π2 either in
accordance with Lemma 4.3 or Lemma 4.4, but in this case we exchange the meaning of
colours a, b. Namely, we substitute a by b and b by a in each value of L2 (given by the
corresponding lemma).
Observe that the assumptions on numbers k1, k2, k3 and the fact that P2 has only 2-
edges imply that L1 = L2 on vertices of P2. Define an f -assignment L for H such that
L(v) =

L1(v), if v ∈ V (C1) \ V (P2),
L2(v), if v ∈ V (C2) \ V (P2),
L1(v) = L2(v), if v ∈ V (P2).
Suppose, for a contradiction, that ϕ is a proper L-colouring of H. Fact 3.1 implies that
ϕ|V (C1) is a proper L1-colouring of C1 and ϕ|V (C2) is a proper L2-colouring of C2. By
Lemma 4.3 or Lemma 4.4 (depending on the parity of k1 + k2) we have ϕ(v1) = b and
by one of Lemmas 4.3, 4.4 (depending on the parity of k2 + k3) we have ϕ(v1) = a, a
contradiction.
For forthcoming Lemmas 4.6, 4.7, 4.8, 4.9, 4.10, we introduce the following notations.
Let P be a hyperpath on at least two vertices and let v1, . . . , vn be a canonical ordering of
V (P). Next let f∗ : V (P) → N be defined by f∗(v) = degP(v) for v /∈ {v1, vn} and
f∗(v1) = f
∗(vn) = 2.
Giving an f∗-assignment L for P and (α, γ) ∈ L(v1)×L(vn), we say that a pair (α, γ)
is extendable (for P) if there is a proper L-colouring ϕ of P such that ϕ(v1) = α, ϕ(vn) =
γ. The pair (α, γ) ∈ L(v1)×L(vn) that is not extendable for P is called forbidden (for P).
The next lemma is a generalization of the lemma that was proven in [3].
Lemma 4.6. Let P be a hyperpath on at least two vertices, let v1, . . . , vn be a canonical or-
dering of V (P) and let {vi1 , . . . , vik} be the set of all vertices of degree two in P with ip <
is for p < s. If L is an f∗-assignment for P such that L(v1), L(vi1), . . . , L(vik), L(vn)
are not identical, then at most one pair in L(v1)× L(vn) is forbidden for P .
Proof. We will show that at most one pair in L(v1) × L(vn) is forbidden for the path
P , where V (P ) = {v1 = vi0 , vi1 , . . . , vik , vn = vik+1} and E(P ) = {vijvij+1 : j ∈
{0, . . . , k}}. Note that P is a graph. Since every proper L|V (P )-colouring of P can be
extended to a proper L-colouring of P , the lemma will follow. We prove this statement by
the induction on the number of edges in P (the number k + 1). Observe that it is true for
a path P with one edge. Suppose that |E(P )| ≥ 2. Since the lists of v1, vi1 , . . . , vik , vn
are not identical, the lists of v1, vi1 , . . . , vik or the lists of vi1 , . . . , vik , vn are not identical
either. Say the lists of vi1 , . . . , vik , vn are not identical. Let L(v1) = {a, b}, L(vn) =
92 Ars Math. Contemp. 22 (2022) #P1.05 / 83–97
{c, d}, L(vi1) = {α, β} and assume that a ̸= β and b ̸= α. By inductive assumptions, at
least three pairs in L(vi1)×L(vn) are extendable for P−v1, say (α, c), (α, d), (β, c). Thus
pairs (b, c), (b, d), (a, c) are extendable for P , and hence, they are extendable for P .
Lemma 4.7. If P is a hyperpath with at least one 3+-edge, v1, . . . , vn is a canonical
ordering of V (P) and L is an f∗-assignment for P , then at most one pair in L(v1)×L(vn)
is forbidden for P .
Proof. We prove the assertion by the induction on the number of edges in E(P). Observe
that the lemma trivially holds when P has one edge. Suppose that P is a hyperpath with at
least one 3+-edge and |E(P)| ≥ 2. Let {vi1 , . . . , vik} be the set of all vertices of degree
two in P with ip < is for p < s. If the lists of v1, vi1 , . . . , vik , vn are not identical, then
the statement follows from Lemma 4.6. Thus we may assume that L(v1) = L(vi1) =
· · · = L(vik) = L(vn) = {a, b}. Let E1 = {v1, v2, . . . , vi1}. Renaming vertices, if it is
necessary, we may assume that P ′ = P \ {v1, . . . , vi1−1} contains a 3+-edge. Thus P ′ is
a hyperpath satisfying inductive assumptions, and so, at least three pairs in L(vi1)×L(vn)
are extendable for P ′. Note that if we colour v1 with a and vi1 with b or if we colour v1
with b and vi1 with a, then we can extend such a colouring to a proper L-colouring of P .
Hence, in L(v1)× L(vn) there are three pairs that are extendable for P .
Lemmas 4.6, 4.7 immediately imply the following fact.
Lemma 4.8. If P is a hyperpath on at least two vertices, v1, . . . , vn is a canonical ordering
of V (P) and L is an f∗-assignment for P , then at most two pairs in L(v1) × L(vn) are
forbidden for P . Moreover,
i) exactly two pairs are forbidden for P if and only if P contains only 2-edges and
L(v1) = · · · = L(vn), and
ii) if there are exactly two forbidden pairs for P and P is of even length and L(v1) =
{a, b}, then (a, a) and (b, b) are extendable for P , and
iii) if there are exactly two forbidden pairs for P and P is of odd length and L(v1) =
{a, b}, then (a, b) and (b, a) are extendable for P .
Lemma 4.9. If P is a hyperpath of length two, v1, . . . , vn is a canonical ordering of
V (P), L is an f∗-assignment for P and L(v1) = L(vn) = {a, b}, then (a, a) and (b, b)
are extendable for P .
Based on Lemmas 4.6, 4.7, 4.8, 4.9 we have the following result.
Lemma 4.10. Let k1, k2, k3 ∈ N. If θhk1,k2,k3 is sc-greedy, then one of the hyperpaths of
θhk1,k2,k3 , say the hyperpath of length k2, has only 2-edges, and, under this assumption, one
of the following conditions is satisfied:
i) k1 + k2 and k2 + k3 are odd numbers and at least one of the inequalities k1 ≥ 2,
k3 ≥ 2 holds, or
ii) k1 + k2 is an odd number and k2 + k3 is an even number and k3 ≥ 3, or
iii) k1 + k2 is an even number and k2 + k3 is an even number and k1 ≥ 3 and k3 ≥ 3.
E. Drgas-Burchardt et al.: Sum-list-colouring of θ-hypergraphs 93
Proof. Let H = θhk1,k2,k3 . Suppose that for each possible permutation ki1 , ki2 , ki3 of
numbers k1, k2, k3 either the hyperpath of H of length ki2 contains 3+-edge or θhki1 ,ki2 ,ki3
satisfies no of the conditions i), ii), iii) of the lemma. The aim is to prove that H is not
sc-greedy. We may assume that at most one of the numbers k1, k2, k3 is equal to one.
Otherwise, H is not linear and the statement follows by Fact 3.7. We define f so that
f(v) = 1 if degH(v) = 1 and f(v) = 2 if degH(v) ≥ 2. Next, we will show that for
each f -assignment L for H there is a proper L-colouring of H. Since
∑
v∈V (H) f(v) =
GB(H) − 1, the theorem will follow. Let P1,P2,P3 be the hyperpaths of H of lengths
k1, k2, k3, respectively, and let v1, vn be vertices of degree 3 in H. Let L be an arbitrary
f -assignment for H. First observe that if each hyperpath Pi, i ∈ {1, 2, 3}, has at least
one 3+-edge, then for each hyperpath Pi at most one pair in L(v1) × L(vn) is forbidden,
by Lemma 4.7. Since we have four possible pairs in L(v1) × L(vn), at least one pair can
be extended to a proper L-colouring of H. Thus at least one hyperpath contains only 2-
edges, so it is the path. Moreover, the lists of vertices of this path must be identical, by
Lemma 4.8 i). We may assume that each vertex of this path has the list {a, b}, and so,
L(v1) = L(vn) = {a, b}. Let us consider two cases.
Case 1. The numbers k1, k2, k3 are all of the same parity. Definitely, H does not fulfill
neither the property i) nor ii). Since H does not have the property iii) either, at least one of
integers k1, k2, k3 is less than or equal to two. Assume that k1 ≤ 2.
Subcase 1.1. All of the numbers k1, k2, k3 are even. Thus k1 = 2. If k2 ≥ 3 and k3 ≥ 3,
then P1 has to contain at least one 3+-edge. Otherwise, H satisfies iii) for a permutation
ki1 , ki2 , ki3 , where ki2 = k1. By our initial assumption P2 or P3 has only 2-edges and
pairs (a, a), (b, b) are extendable for this path, by Lemma 4.8 ii). Without loss of generality
assume that P2 contains only 2-edges and pairs (a, a), (b, b) are extendable for P2. Note
that pairs (a, a), (b, b) are also extendable for P1, by Lemma 4.9. From Lemma 4.8, at
most two pairs are forbidden for P3, and if exactly two pairs are forbidden for P3, then
(a, a), (b, b) are extendable for P3. Thus both pairs (a, a), (b, b) can be extended to a
proper L-colouring of H. If at most one pair is forbidden for P3, then at least one of pairs
(a, a), (b, b) can be extended to a proper L-colouring of H.
Now suppose that at least two hyperpaths have lengths two, say k1 = 2 and k2 = 2.
From Lemma 4.9, (a, a) and (b, b) are extendable for both P1 and P2. From Lemma 4.8, at
most two pairs are forbidden for P3. If exactly two pairs are forbidden for P3, then again
by Lemma 4.8 ii), both pairs (a, a), (b, b) are extendable for P3. Otherwise, at most one
pair is forbidden for P3. Thus (a, a) or (b, b) is extendable for all P1, P2, P3.
Subcase 1.2. All of the numbers k1, k2, k3 are odd. Thus k1 = 1. Since H is linear, we
have k2 ≥ 3 and k3 ≥ 3. Furthermore, P1 is a 3+-edge, otherwise, H satisfies iii). Again,
without loss of generality, assume that P2 contains only 2-edges and pairs (a, b), (b, a) are
extendable for P2, by Lemma 4.8 iii). Thus (a, b), (b, a) are extendable for both P1, P2.
If there is at most one pair forbidden for P3, then one of pairs (a, b), (b, a) is extendable
for all P1, P2, P3. Otherwise, two pairs are forbidden for P3, however, then both pairs
(a, b), (b, a) are extendable for P3, by Lemma 4.8 iii). So, both pairs (a, b), (b, a) can be
extended to a proper L-colouring of H.
Case 2. The numbers k1, k2, k3 are not of the same parity. In this case either one hyperpath
in {P1,P2,P3} is of odd length and two of them are of even length or one hyperpath in
{P1,P2,P3} is of even length and two are of odd length. So, H does not have the property
94 Ars Math. Contemp. 22 (2022) #P1.05 / 83–97
iii). The hyperpath of odd length in the first case and the hyperpath of even length in the
second case has a 3+-edge, since otherwise, H has the property i). Let us consider the
following two possible subcases.
Subcase 2.1. The number k1 is odd and P1 has a 3+-edge, k2, k3 are even. Since H
does not have the property ii), k2 = 2 or k3 = 2. Say k3 = 2. If k2 > 2, then P3 has
3+-edge, as otherwise, H has the property ii). Thus P2 must have only 2-edges and pairs
(a, a), (b, b) are extendable for P2, by Lemma 4.8 ii). From Lemma 4.9, pairs (a, a), (b, b)
are extendable for P3, so, (a, a), (b, b) are extendable for both P2, P3. By Lemma 4.7, at
most one of these pairs is forbidden for P1, so there is a proper L-colouring of H. Suppose
now that k2 = 2, so we have k2 = k3 = 2. From Lemma 4.9 both pairs (a, a), (b, b)
are extendable for both P2, P3. Since at most one of these pairs is forbidden for P1, the
statement follows.
Subcase 2.2. The number k1 is even and P1 has a 3+-edge, k2, k3 are odd. Since H does
not have the property ii), k2 = 1 or k3 = 1. Say k3 = 1. Furthermore, the previous
consideration leads to k2 ≥ 3. If P3 has exactly 2-edge, then H has the property ii). Thus
P3 must have a 3+-edge, and so, P2 must have only 2-edges. Hence, pairs (a, b), (b, a)
are extendable for P2. Thus (a, b) and (b, a) are extendable for both P2, P3. Furthermore,
at most one of pairs is forbidden for P1, and so, at least one of the pairs (a, a), (b, b) is
extendable for all P1, P2, P3, which creates a proper L-colouring of H and proves the
lemma.
Now, we are in a position to present the main result of the paper that immediately
follows from Lemmas 4.5, 4.10. Next, the consequence of this result is formulated.
Theorem 4.11. Let k1, k2, k3 ∈ N. A hypergraph θhk1,k2,k3 is sc-greedy if and only if one
of the hyperpaths of θhk1,k2,k3 , say the hyperpath of length k2, has only 2-edges and, under
this assumption, one of the following conditions holds:
i) k1 + k2 and k2 + k3 are odd numbers and at least one of the inequalities k1 ≥ 2,
k3 ≥ 2 holds, or
ii) k1 + k2 is an odd number and k2 + k3 is an even number and k3 ≥ 3, or
iii) k1 + k2 is an even number and k2 + k3 is an even number and k1 ≥ 3 and k3 ≥ 3.
Note that for arbitrary parameters k1, k2, k3 such that (k1, k2, k3) ̸= (1, 1, 1) and arbi-
trary vertex of θhk1,k2,k3 each component of θ
h
k1,k2,k3
− v is in F . Hence the following fact
is valid.
Corollary 4.12. If k1, k2, k3 ∈ N and at most two of the numbers k1, k2, k3 are equal to
one, then θhk1,k2,k3 ∈ C(Γsc) if and only if θ
h
k1,k2,k3
/∈ Γsc.
5 Concluding remarks and open problems
A connected hypergraph is 2-connected if it cannot be a result of identification of a vertex
of H1 and a vertex of H2, where H1, H2 are some disjoint hypergraphs, each on at least
two vertices.
Note that, based on Fact 3.2 and Theorem 3.9, both, the union operation and the iden-
tification operation (applied to vertices of two disjoint hypergraphs) keep sc-greediness of
E. Drgas-Burchardt et al.: Sum-list-colouring of θ-hypergraphs 95
hypergraphs. Hence, analyzing sc-greediness of hypergraphs it is enough to focus on 2-
connected ones. Additionally, each sc-greedy hypergraph must be linear, by Fact 3.7. Thus
the following question seems to be interesting.
Problem 5.1. How to characterize all hypergraphs in Γsc that are 2-connected and linear?
To support the discussion this question we start with some notes concerning graphs.
The famous theorem that characterizes all linear (equivalently, simple) 2-connected graphs
can be found in [4]. To cite it we need the following notion.
Let G be a graph on at least two vertices. By adding a G-path to G, we mean the result
of two operations of identification applied to the graph G and an arbitrary path P with a
canonical ordering v1, . . . , vn of V (P ), n ≥ 2 (G and P are disjoint). More precisely, it is
a result of identification of v1 and x and also vn and y, where x, y are two different vertices
of G.
Lemma 5.2 ([4]). A simple graph is 2-connected if and only if it can be constructed from
a cycle by successively adding G-paths to graphs G already constructed.
Observe that each cycle is 2-connected and sc-greedy. Next, adding a G-path to the
cycle G we obtain a θ-graph. Theorem 4.1 characterizes all θ-graphs that are in Γsc. The
question is, whether we should expect that an sc-greedy graph be obtained by adding a
G-path to an sc-greedy θ-graph. In [3] the authors proved that χsc(G) + 2s ≤ χsc(G1) ≤
χsc(G) + 2s + 1 if G1 is the result of adding a G-path on s + 2 vertices to an arbitrary
simple graph G, assuming that s ≥ 1. They did not consider the case when a G-path has
2 vertices, which seems to be very important. However, based on this observation, they
gave the characterization of all graphs in Γsc that are generalized θ-graphs. For r ≥ 3, a
generalized θ-graph is a simple graph, denoted by θk1,k2,...,kr , consisting of two vertices
connected by r internally vertex disjoint paths of lengths k1, k2, . . . , kr. In [3] the authors
showed that θk1,k2,...,kr is not sc-greedy if r ≥ 5. Moreover, θk1,k2,k3,k4 is not sc-greedy
if and only if it contains an induced subgraph θ2,2,ki with even ki and i ∈ {3, 4} or, if all
numbers k1, k2, k3, k4 have the same parity. It follows that starting with a θ-graph G and
adding a G-path two times, in this special case (to obtain a generalized θ-graph), we always
obtain a graph that is not sc-greedy. On the other hand, the graph presented in Figure 1 that
needs to be added a G-path 3 times is still sc-greedy (see the graph G10,12 in [10]). It leads
to formulating the following problem.
Figure 1: An sc-greedy graph that needs the application of adding a G-path 3 times.
Problem 5.3. Under which conditions can we obtain an sc-greedy graph by adding a G-
path to an sc-greedy graph G?
In a way similar for graphs we can define the operation of adding an H-path to a hy-
pergraph H and pose the problem similar to Problem 5.3 in the class of hypergraphs.
96 Ars Math. Contemp. 22 (2022) #P1.05 / 83–97
Problem 5.4. Under which conditions can we obtain an sc-greedy hypergraph by adding
an H-path to an sc-greedy hypergraph H?
Unfortunately, there are 2-connected linear hypergraphs that cannot be obtained from a
hypercycle by successively adding H-paths.
On the other hand, there is a relatively large subclass of the class of 2-connected lin-
ear hypergraphs, for which, the problem of belonging to Γsc can be solved, with help of
consideration concerning graphs.
A hypergraph G is a blown of a graph G if G is a result of a substitution of each edge
of G by a 3+-edge of G that contains vertices of substituted edge of G (see for example
Figure 2). Let F ′ be the class consisting of all hypergraphs that are all possible blowns
of 2-connected graphs, except cycles. Clearly, every hypergraph in F ′ is 2-connected, by
definition.
Figure 2: A graph and its blown.
Theorem 5.5. No hypergraph in F ′ is sc-greedy.
Proof. First observe that if H ∈ F ′, then H is a blown of some 2-connected graph H that
is not a cycle. From Lemma 5.2, H contains a subgraph that is a θ-graph. By the defini-
tion of F ′ we know that H contains an induced subhypergraph H′ that is a θ-hypergraph,
and moreover, H′ has no hyperpath having only 2-edges. Thus H′ is not sc-greedy, by
Lemma 4.10. Finally, H is not sc-greedy, since Γsc is closed when taking induced subhy-
pergraphs.
It is worth mentioning that hypergraphs in F ′ can or cannot be blowns of sc-greedy
graphs. It follows that probably, to be an sc-greedy hypergraph is a relatively rare fea-
ture in the class of hypergraphs with only 3+-edges. It motivates the following separate
subproblem of Problem 5.1.
Problem 5.6. How to characterize all hypergraphs in Γsc that are 2-connected, linear and
have only 3+-edges.
Finally, observe that each hypergraph in C(Γsc) is 2-connected, but this class includes
linear and non-linear hypergraphs. Thus, referring to the C(Γsc) class, we obtain the fol-
lowing open question and its subquestion.
Problem 5.7. How to characterize all hypergraphs in C(Γsc)?
Problem 5.8. How to characterize all non-linear hypergraphs in C(Γsc)?
E. Drgas-Burchardt et al.: Sum-list-colouring of θ-hypergraphs 97
ORCID iDs
Ewa Drgas-Burchardt https://orcid.org/0000-0001-6229-177X
Elżbieta Sidorowicz https://orcid.org/0000-0002-7774-0512
References
[1] C. Berge, Hypergraphs: Combinatorics of Finite Sets, volume 45 of North-Holland Mathemat-
ical Library, North-Holland, Amsterdam, 1989.
[2] A. Berliner, U. Bostelmann, R. A. Brualdi and L. Deaett, Sum list coloring graphs, Graphs
Combin. 22 (2006), 173–183, doi:10.1007/s00373-005-0645-9.
[3] C. Brause, A. Kemnitz, M. Marangio, A. Pruchnewski and M. Voigt, Sum choice number of
generalized θ-graphs, Discrete Math. 340 (2017), 2633–2640, doi:10.1016/j.disc.2016.11.028.
[4] R. Diestel, Graph Theory, volume 173 of Graduate Texts in Mathematics, Springer-Verlag,
New York, 2nd edition, 2000, doi:10.1007/b100033.
[5] E. Drgas-Burchardt and A. Drzystek, General and acyclic sum-list-colouring of graphs, Appl.
Anal. Discrete Math. 10 (2016), 479–500, doi:10.2298/aadm161011026d.
[6] P. Erdős, A. L. Rubin and H. Taylor, Choosability in graphs, in: P. Z. Chinn and D. McCarthy
(eds.), Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Com-
puting, Utilitas Mathematica, Winnipeg, Man., volume XXVI of Congressus Numerantium,
1980 pp. 125–157, held at Humboldt State University, Arcata, Calif., September 5 – 7, 1979.
[7] B. Heinold, Sum list coloring and choosability, Ph.D. thesis, Lehigh University, 2006.
[8] G. Isaak, Sum list coloring 2 × n arrays, Electron. J. Combin. 9 (2002), #N8, 7 pp., doi:
10.37236/1669.
[9] G. Isaak, Sum list coloring block graphs, Graphs Combin. 20 (2004), 499–506, doi:10.1007/
s00373-004-0564-1.
[10] A. Kemnitz, M. Marangio and M. Voigt, Sum list colorings of small graphs, Congr. Numer. 227
(2016), 27–50.
[11] J. Kratochvı́l, Zs. Tuza and M. Voigt, New trends in the theory of graph colorings: choosability
and list coloring, in: R. L. Graham, J. Kratochvı́l and F. S. Roberts (eds.), Contemporary
Trends in Discrete Mathematics, American Mathematical Society, Providence, RI, volume 49
of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 183–197,
1999, doi:10.1090/dimacs/049/13, proceedings of the DIMATIA-DIMACS Conference on The
Future of Discrete Mathematics held at Štiřı́n Castle, May 19 – 25, 1997.
[12] M. Lastrina, List-coloring and sum-list-coloring problems on graphs, Ph.D. thesis, Iowa State
University, 2012.