Geodesic
Hypergraph operations preserving sc-greediness
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1217-1241

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 exists a proper vertex colouring ϕ of ℋ such that ϕ(v)∈ L(v) for all v∈ V(ℋ), where L: V(ℋ)⟶ 2^ℕ is an assignment of f(v) colours to a vertex v. The sum-choice-number χ_sc(ℋ) of ℋ is a minimum ∑_v∈ V( ℋ)f(v) taken over all functions f such that ℋ is f-choosable. The hypergraphs for which χ_sc( ℋ)=|V( ℋ)|+| ℰ( ℋ)| are called sc-greedy. The class of sc-greedy hypergraphs is closed under the union of hypergraphs having at most one vertex in common. In this paper we consider sc-greediness of the union of hypergraphs having two vertices in common. We investigate this operation when one of the arguments is an arbitrary sc-greedy hypergraph while the second one is a hyperpath. Our research is motivated by the possibility of obtaining improved bounds on the sum-choice-number of graphs and new applications to the resource allocation problems in computer systems.
Keywords: hypergraph, list colouring, generalized colouring, minimum sum, resource allocation, greedy algorithm 
@article{DMGT_2024_44_3_a19,
     author = {Borowiecki, Piotr and Drgas-Burchardt, Ewa and Sidorowicz, El\.zbieta},
     title = {Hypergraph operations preserving sc-greediness},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1217--1241},
     publisher = {mathdoc},
     volume = {44},
     number = {3},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a19/}
}
TY  - JOUR
AU  - Borowiecki, Piotr
AU  - Drgas-Burchardt, Ewa
AU  - Sidorowicz, Elżbieta
TI  - Hypergraph operations preserving sc-greediness
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1217
EP  - 1241
VL  - 44
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a19/
LA  - en
ID  - DMGT_2024_44_3_a19
ER  - 
%0 Journal Article
%A Borowiecki, Piotr
%A Drgas-Burchardt, Ewa
%A Sidorowicz, Elżbieta
%T Hypergraph operations preserving sc-greediness
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1217-1241
%V 44
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a19/
%G en
%F DMGT_2024_44_3_a19
Borowiecki, Piotr; Drgas-Burchardt, Ewa; Sidorowicz, Elżbieta. Hypergraph operations preserving sc-greediness. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1217-1241. http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a19/