- Tytuł:
- Generalized Hypergraph Coloring
- Autorzy:
- Schweser, Thomas
- Powiązania:
- https://bibliotekanauki.pl/articles/32083810.pdf
- Data publikacji:
- 2021-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
hypergraph decomposition
vertex partition
degeneracy
coloring of hypergraphs
hypergraph properties - Opis:
- A smooth hypergraph property \(\mathcal{P}\) is a class of hypergraphs that is hereditary and non-trivial, i.e., closed under induced subhypergraphs and it contains a non-empty hypergraph but not all hypergraphs. In this paper we examine \(\mathcal{P}\)-colorings of hypergraphs with smooth hypergraph properties \(\mathcal{P}\). A \(\mathcal{P}\)-coloring of a hypergraph $H$ with color set $C$ is a function $\varphi : V(H) → C$ such that \(H\big[\varphi^{−1}(c)\big]\) belongs to \(\mathcal{P}\) for all $c ∈ C$. Let $L : V (H) → 2^C$ be a so called list-assignment of the hypergraph $H$. Then, a (\(\mathcal{P}, L\))-coloring of $H$ is a \(\mathcal{P}\)-coloring $\varphi$ of $H$ such that $\varphi(v) ∈ L(v)$ for all $v ∈ V (H)$. The aim of this paper is a characterization of (\(\mathcal{P}, L\))-critical hypergraphs. Those are hypergraphs $H$ such that $H − v$ is (\(\mathcal{P}, L\))-colorable for all $v ∈ V (H)$ but $H$ itself is not. Our main theorem is a Gallai-type result for critical hypergraphs, which implies a Brooks-type result for (\(\mathcal{P}, L\))-colorable hypergraphs. In the last section, we prove a Gallai-type bound for the degree sum of (\(\mathcal{P}, L\))-critical locally simple hypergraphs.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 103-121
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł