Geodesic
Hypergraph operations preserving sc-greediness
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1217-1241 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2024},
     volume = {44},
     number = {3},
     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
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
%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/

[1] C. Berge, Hypergraphs: Combinatorics of Finite Sets (North-Holland, Amsterdam, 1989).

[2] P. Borowiecki, Computational aspects of greedy partitioning of graphs, J. Comb. Optim. 35 (2018) 641–665. https://doi.org/10.1007/s10878-017-0185-2

[3] P. Borowiecki, On-line partitioning for on-line scheduling with resource conflicts, in: Proc. 7th Int. Conf. on Parallel Processing and Applied Mathematics (PPAM'07), Lecture Notes in Comput. Sci. 4967, R. Wyrzykowski, J. Dongarra, K. Karczewski and J. Wasniewski (Ed(s)), (Springer, Berlin, Heidelberg 2007) 981–990. https://doi.org/10.1007/978-3-540-68111-3_104

[4] P. Borowiecki and E. Sidorowicz, Dynamic F-free coloring of graphs, Graphs Combin. 34 (2018) 457–475. https://doi.org/10.1007/s00373-018-1886-8

[5] P. Borowiecki and E. Sidorowicz, Dynamic coloring of graphs, Fund. Inform. 114 (2012) 105–128. https://doi.org/10.3233/FI-2012-620

[6] C. Brause, A. Kemnitz, M. Marangio, A. Pruchnewski and M. Voigt, Sum choice number of generalized \theta-graphs, Discrete Math. 340 (2017) 2633–2640. https://doi.org/10.1016/j.disc.2016.11.028

[7] R. Diestel, Graph Theory, Grad. Texts in Math. 173 (Springer, Berlin, Heidelberg, 2017). https://doi.org/10.1007/978-3-662-53622-3

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

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

[10] E. Drgas-Burchardt, A. Drzystek and E. Sidorowicz, Sum-list-coloring of \theta-hypergraphs, Ars Math. Contemp. 22 (2022) #P1.05. https://doi.org/10.26493/1855-3974.2083.e80

[11] E. Drgas-Burchardt and E. Sidorowicz, Sum-list colouring of unions of a hypercycle and a path with at most two vertices in common, Discuss. Math. Graph Theory 40 (2020) 893–917. https://doi.org/10.7151/dmgt.2312

[12] P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, in: Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congr. Numer. 26 (1979) 125–157.

[13] B. Heinold, Sum List Coloring and Choosability, PhD Thesis (Lehigh University, 2006).

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

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

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

[17] M. Kubale, Graph Colorings, Contemp. Math. 352 (American Mathematical Society, 2004). https://doi.org/10.1090/conm/352

[18] M. Lastrina, List-Coloring and Sum-List-Coloring Problems on Graphs, PhD Thesis (Iowa State University, 2012). https://doi.org/10.31274/etd-180810-1195

[19] C. Thomassen, Every planar graph is 5-choosable, J. Combin. Theory Ser. B 62 (1994) 180–181. https://doi.org/10.1006/jctb.1994.1062