Article in volume
Authors:
Title:
Hypergraph operations preserving sc-greediness
PDFSource:
Discussiones Mathematicae Graph Theory 44(3) (2024) 1217-1241
Received: 2023-08-22 , Revised: 2023-11-30 , Accepted: 2023-11-30 , Available online: 2023-12-16 , https://doi.org/10.7151/dmgt.2533
Abstract:
Given a hypergraph ${\cal H}$ and a function $f:V({\cal H})\longrightarrow \mathbb{N}$,
we say that ${\cal H}$ is $f$-choosable if there exists a proper vertex colouring
$\phi$ of ${\cal H}$ such that $\phi(v)\in L(v)$ for all $v\in V({\cal H})$, where
$L: V({\cal H})\longrightarrow 2^{\mathbb{N}}$ is an assignment of $f(v)$ colours to
a vertex $v$. The sum-choice-number $\chi_{sc}({\cal H})$ of ${\cal H}$ is a minimum
$\sum_{v\in V({\cal H})}f(v)$ taken over all functions $f$ such that ${\cal H}$ is
$f$-choosable. The hypergraphs for which $\chi_{sc}({\cal H})=|V({\cal H})|+|{\cal E}({\cal H})|$
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
References:
- C. Berge, Hypergraphs: Combinatorics of Finite Sets (North-Holland, Amsterdam, 1989).
- 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 - 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 - 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 - P. Borowiecki and E. Sidorowicz, Dynamic coloring of graphs, Fund. Inform. 114 (2012) 105–128.
https://doi.org/10.3233/FI-2012-620 - 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 - R. Diestel, Graph Theory, Grad. Texts in Math. 173 (Springer, Berlin, Heidelberg, 2017).
https://doi.org/10.1007/978-3-662-53622-3 - 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 - 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 - 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 - 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 - 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.
- B. Heinold, Sum List Coloring and Choosability, PhD Thesis (Lehigh University, 2006).
- G. Isaak, Sum list coloring block graphs, Graphs Combin. 20 (2004) 499–506.
https://doi.org/10.1007/s00373-004-0564-1 - G. Isaak, Sum list coloring $2× n$ arrays, Electron. J. Combin. 9 (2002) #N8.
https://doi.org/10.37236/1669 - 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 - M. Kubale, Graph Colorings, Contemp. Math. 352 (American Mathematical Society, 2004).
https://doi.org/10.1090/conm/352 - 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 - 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
Close