Geodesic
Generalized Hypergraph Coloring
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 103-121.

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

A smooth hypergraph property 𝒫 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 𝒫-colorings of hypergraphs with smooth hypergraph properties 𝒫. A 𝒫-coloring of a hypergraph H with color set C is a function φ : V(H) → C such that H[φ^−1(c)] belongs to 𝒫 for all c ∈ C. Let L : V (H) → 2^C be a so called list-assignment of the hypergraph H. Then, a (𝒫, L)-coloring of H is a 𝒫-coloring φ of H such that φ(v) ∈ L(v) for all v ∈ V (H). The aim of this paper is a characterization of (𝒫, L)-critical hypergraphs. Those are hypergraphs H such that H − v is (𝒫, 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 (𝒫, L)-colorable hypergraphs. In the last section, we prove a Gallai-type bound for the degree sum of (𝒫, L)-critical locally simple hypergraphs.
Keywords: hypergraph decomposition, vertex partition, degeneracy, coloring of hypergraphs, hypergraph properties 
@article{DMGT_2021_41_1_a6,
     author = {Schweser, Thomas},
     title = {Generalized {Hypergraph} {Coloring}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {103--121},
     publisher = {mathdoc},
     volume = {41},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a6/}
}
TY  - JOUR
AU  - Schweser, Thomas
TI  - Generalized Hypergraph Coloring
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 103
EP  - 121
VL  - 41
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a6/
LA  - en
ID  - DMGT_2021_41_1_a6
ER  - 
%0 Journal Article
%A Schweser, Thomas
%T Generalized Hypergraph Coloring
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 103-121
%V 41
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a6/
%G en
%F DMGT_2021_41_1_a6
Schweser, Thomas. Generalized Hypergraph Coloring. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 103-121. http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a6/

[1] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survery of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5–50. doi: 10.7151/dmgt.1037

[2] M. Borowiecki, I. Broere and P. Mihók, On generalized list colourings of graphs, Discuss. Math. Graph Theory 17 (1995) 127–132. doi: 10.7151/dmgt.1045

[3] M. Borowiecki, E. Drgas-Burchardt and P. Mihók, Generalized list colouring of graphs, Discuss. Math. Graph Theory 15 (1995) 185–193. doi: 10.7151/dmgt.1016

[4] R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc., Math. Phys. Sci. 37 (1941) 194–197.

[5] E.J. Cockayne, Colour classes for r-graphs, Canad. Math. Bull. 15 (1972) 349–354. doi: 10.4153/CMB-1972-063-2

[6] G.A. Dirac, A property of 4- chromatic graphs and some remarks on critical graphs, J. Lond. Math. Soc. 27 (1952) 85–92. doi: 10.1112/jlms/s1-27.1.85

[7] G.A. Dirac, The structure of k-chromatic graphs, Fund. Math. 40 (1953) 42–55. doi: 10.4064/fm-40-1-42-55

[8] P. Erdős and A. Hajnal, On the chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966) 61–99. doi: 10.1007/BF02020444

[9] P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. XXVI (1979) 125–157.

[10] T. Gallai, Kritische Graphen II, Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963) 373–395.

[11] R.P. Jones, Brooks’ theorem for hypergraphs, in: Proc. 5th British Combinatorial Conf. (1975) 379–384.

[12] A.V. Kostochka and M. Stiebitz, A new lower bound on the number of edges in colour-critical graphs and hypergraphs, J. Combin. Theory Ser. B 87 (2003) 374–402. doi: 10.1016/S0095-8956(02)00035-7

[13] A.V. Kostochka, M. Stiebitz and B. Wirth, The colour theorems of Brooks and Gallai extended, Discrete Math. 191 (1996) 125–137. doi: 10.1016/S0012-365X(98)00100-9

[14] L. Lovász, On chromatic number of finite set-systems, Acta Math. Acad. Sci. Hungar. 19 (1968) 59–67. doi: 10.1007/BF01894680

[15] P. Mihók and R. Škrekovski, Gallai's inequality for critical graphs of reducible hereditary properties, Discuss. Math. Graph Theory 21 (2001) 167–177. doi: 10.7151/dmgt.1141

[16] T. Schweser and M. Stiebitz, Hypergraph partitions and variable degeneracy, (2017) preprint. arXiv:1804.04894

[17] V.G. Vizing, Vertex coloring with given colors, Diskret. Analiz. 29 (1976) 3–10, in Russian.