Geodesic
On proper colorings of hypergraphs
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part III, Tome 391 (2011), pp. 79-89 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Let $\mathcal H$ be a hypergraph with maximal vertex degree $\Delta$, such that each hyperedge of it has at least $\delta$ vertices. Let $k=\lceil\frac{2\Delta}\delta\rceil$. We prove that $\mathcal H$ admits a proper vertex coloring with $k+1$ colors, (i.e., in any hyperedge there should be at least two vertices of different colors). For $k\ge3$ and $\delta\ge3$ we prove that $\mathcal H$ admits a proper vertex coloring with $k$ colors. For a graph $G$ set $k=\lceil\frac{2\Delta(G)}{\delta(G)}\rceil$. As a corollary we derive that there exists a proper dynamic coloring of the graph $G$ with $k+1$ colors, and for $k\ge3$ and $\delta(G)\ge3$ – with $k$ colors. 
@article{ZNSL_2011_391_a4,
     author = {N. V. Gravin and D. V. Karpov},
     title = {On proper colorings of hypergraphs},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {79--89},
     year = {2011},
     volume = {391},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2011_391_a4/}
}
TY  - JOUR
AU  - N. V. Gravin
AU  - D. V. Karpov
TI  - On proper colorings of hypergraphs
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2011
SP  - 79
EP  - 89
VL  - 391
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2011_391_a4/
LA  - ru
ID  - ZNSL_2011_391_a4
ER  - 
%0 Journal Article
%A N. V. Gravin
%A D. V. Karpov
%T On proper colorings of hypergraphs
%J Zapiski Nauchnykh Seminarov POMI
%D 2011
%P 79-89
%V 391
%U http://geodesic.mathdoc.fr/item/ZNSL_2011_391_a4/
%G ru
%F ZNSL_2011_391_a4
N. V. Gravin; D. V. Karpov. On proper colorings of hypergraphs. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part III, Tome 391 (2011), pp. 79-89. http://geodesic.mathdoc.fr/item/ZNSL_2011_391_a4/

[1] G. Agnarsson, M. M. Halldoŕsson, “Strong Colorings of Hypergraphs”, Approximation and Online Algorithms, Lecture Notes in Computer Science, 3351, 2005, 253–266 | DOI | MR | Zbl

[2] N. Alon, Z. Bregman, “Every 8-uniform 8-regular hypergraph is 2-colorable”, Graphs Combinat., 4 (1988), 303–305 | DOI | MR

[3] N. Alon, J. Spencer, The probabilistic method, Wiley-Interscience, New York, 2000 | MR | Zbl

[4] J. Beck, “On a combinatorial problem of P. Erdős and L. Lovász”, Discrete Math., 17 (1977), 127–131 | DOI | MR | Zbl

[5] J. Beck, “On 3-chromatic hypergraphs”, Discrete Math., 24 (1978), 127–137 | DOI | MR | Zbl

[6] P. Erdős, “On a combinatorial problem”, Nordisk Mat. Tidskr., 11 (1963), 5–10 | MR | Zbl

[7] P. Erdős, “On a combinatorial problem”, Acta Math Acad. Sci. Hungar., 15 (1964), 445–447 | DOI | MR | Zbl

[8] P. Erdős L. Lovász, “Problems and results on 3-chromatic hypergraphs and some related questions”, Infinite and finite sets, Colloq. Math. Soc. J. Bolyai, 10, North Holland, Amsterdam, 1974, 609–627 | MR

[9] L. Hong-Jian, B. Montgomery, H. Poon, “Upper Bounds of Dynamic Chromatic Number”, Ars. Combinatoria, 68 (2003), 193–201 | MR | Zbl

[10] A. Kostochka, “Coloring uniform hypergraphs with few colors”, Random Structures and Algorithms, 24 (2004), 1–10 | DOI | MR | Zbl

[11] A. Pluhár, “Greedy colorings of uniform hypergraphs”, Random Structures and Algorithms, 35 (2009), 216–221 | DOI | MR | Zbl

[12] W. M. Schmidt, “Ein kombinatoriches problem”, Acta Math. Acad. Sci. Hungar., 15 (1964), 373–374 | DOI | MR | Zbl

[13] J. H. Spencer, “Coloring $n$-sets red and blue”, J. Combin Theory Ser. A, 30 (1981), 112–113 | DOI | MR | Zbl

[14] C. Thomassen, “The even cycle problem for directed graphs”, J. Amer. Math. Soc., 5 (1992), 217–229 | DOI | MR | Zbl

[15] N. V. Gravin, “Nevyrozhdennye raskraski v teoreme Bruksa”, Diskr. matem., 21:4 (2009), 105–128 | DOI | MR | Zbl

[16] D. V. Karpov, “Dinamicheskie pravilnye raskraski vershin grafa”, Zap. nauchn. semin. POMI, 381, 2010, 47–77 | MR