Geodesic
Sum-List Colouring of Unions of a Hypercycle and a Path with at Most Two Vertices in Common
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 893-917.

Voir la notice de l'article provenant de la source Library of Science

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 ℋi_sc(ℋ) 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 
@article{DMGT_2020_40_3_a13,
     author = {Drgas-Burchardt, Ewa and Sidorowicz, El\.zbieta},
     title = {Sum-List {Colouring} of {Unions} of a {Hypercycle} and a {Path} with at {Most} {Two} {Vertices} in {Common}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {893--917},
     publisher = {mathdoc},
     volume = {40},
     number = {3},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a13/}
}
TY  - JOUR
AU  - Drgas-Burchardt, Ewa
AU  - Sidorowicz, Elżbieta
TI  - Sum-List Colouring of Unions of a Hypercycle and a Path with at Most Two Vertices in Common
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 893
EP  - 917
VL  - 40
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a13/
LA  - en
ID  - DMGT_2020_40_3_a13
ER  - 
%0 Journal Article
%A Drgas-Burchardt, Ewa
%A Sidorowicz, Elżbieta
%T Sum-List Colouring of Unions of a Hypercycle and a Path with at Most Two Vertices in Common
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 893-917
%V 40
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a13/
%G en
%F DMGT_2020_40_3_a13
Drgas-Burchardt, Ewa; Sidorowicz, Elżbieta. Sum-List Colouring of Unions of a Hypercycle and a Path with at Most Two Vertices in Common. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 893-917. http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a13/

[1] C. Berge, Hypergraphs: Combinatorics of Finite Sets (North-Holland, 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, 5th Ed., Graduate Texts in Mathematics (Springer-Verlag, New York, 2017). doi:10.1007/978-3-662-53622-3

[5] E. Drgas-Burchardt and A. Drzystek, Acyclic sum-list-coloring of grids and other classes of graphs, Opuscula Math. 37 (2017) 535–556. doi:10.7494/OpMath.2017.37.4.535

[6] E. Drgas-Burchardt and A. Drzystek, General and acyclic sum-list-coloring of graphs, Appl. Anal. Discrete Math. 10 (2016) 479–500. doi:10.2298/AADM161011026D

[7] E. Drgas-Burchardt, A. Drzystek and E. Sidorowicz, Sum-list-coloring of θ-hypergraphs, submitted.

[8] B. Heinold, Sum List Coloring and Choosability, Ph.D. Thesis (Lehigh University, 2006).

[9] G. Isaak, Sum list coloring 2 × n arrays, Electron. J. Combin. 9 (2002) #N8. doi:10.37236/1669

[10] G. Isaak, Sum list coloring block graphs, Graphs Combin. 20 (2004) 499–506. doi:10.1007/s00373-004-0564-1

[11] A. Kemnitz, M. Marangio and M. Voigt, Generalized sum list colorings of graphs, Discuss. Math. Graph Theory 39 (2019) 689–703. doi:10.7151/dmgt.2174

[12] A. Kemnitz, M. Marangio and M. Voigt, Sum list colorings of complete multipartite graphs, (2014), preprint.

[13] A. Kemnitz, M. Marangio and M. Voigt, Sum list colorings of small graphs, Congr. Numer. 223 (2015) 45–58.

[14] A. Kemnitz, M. Marangio and M. Voigt, Sum list colorings of wheels, Graphs Combin. 31 (2015) 1905–1913. doi:10.1007/s00373-015-1565-y

[15] A. Kemnitz, M. Marangio and M. Voigt, On the P-sum choice number of graphs for 1-additive properties, Congr. Numer. 229 (2017) 117–124.

[16] M.A. Lastrina, List-Coloring and Sum-List-Coloring Problems on Graphs, Ph.D. Thesis (Iowa State University, 2012).