On proper colourings of hypergraphs using prescribed colours

A. P. Rozovskaya ; D. A. Shabanov

Diskretnaya Matematika, Tome 22 (2010) no. 3, pp. 94-109.

Résumé

We consider a generalisation of the classic combinatorial problem of P. Erdős and A. Hajnal in the theory of hypergraphs to the case of prescribed colourings. We investigate the value $m_{pr}(n,r)$ equal to the minimum number of edges of a hypergraph in the class of $n$-uniform hypergraphs with prescribed chromatic number greater than $r$. We obtain a lower bound for this value which is better than the known results for $r\ge3$. Moreover, we give a sufficient conditions for existence of a prescribed $r$-colourability of an $n$-uniform hypergraph in terms of restrictions on the intersections of edges. As a corollary we obtain a new bound for the characteristic $m_{pr}^*(n,r)$ equal to the minimum number of edges of a hypergraph in the class of $n$-uniform simple hypergraphs (in which any two edges have at most one common vertex) with the prescribed chromatic number greater than $r$.

Bibliographie

[1] Erdős P., Hajnal A., “On a property of families of sets”, Acta Math. Acad. Sci. Hung., 12 (1961), 87–123 | DOI | MR | Zbl

[2] Erdős P., “Some old and new problems in various branches of combinatorics”, Proc. 10th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, 1979, 19–37 | MR

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

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

[5] Kostochka A. V., “Color-critical graphs and hypergraphs with few edges: a survey”, Bolyai Soc. Math. Stud., 15 (2006), 175–198 | MR

[6] Schmidt W. M., “Ein kombinatorisches Problem von P. Erdős and A. Hajnal”, Acta Math. Acad. Sci. Hung., 15 (1964), 373–374 | DOI | MR | Zbl

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

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

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

[10] Radhakrishnan J., Srinivasan A., “Improved bounds and algorithms for hypergraph two-coloring”, Random Structures and Algorithms, 16 (2000), 4–32 | 3.0.CO;2-2 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[11] Alon N., “Hypergraphs with high chromatic number”, Graphs and Combinatorics, 1 (1985), 387–389 | DOI | Zbl

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

[13] Vizing V. G., “Raskraska vershin grafa v predpisannye tsveta”, Metody diskretnogo analiza v teorii kodov i skhem, 29, Institut matematiki SO AN SSSR, Novosibirsk, 1976, 3–10 | MR

[14] Erdős P., Rubin A. L., Taylor H., “Choosability in graphs”, Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, 26, Arcata/Calif., 1980, 125–157 | MR

[15] Erdős P., Lovász L., “Problems and results on 3-chromatic hypergraphs and some related questions”, Colloq. Math. Soc. Janos Bolyai, 10 (1975), 609–627 | MR | Zbl

[16] Szabo Z., “An application of Lovasz local lemma – a new lower bound for the van der Waerden number”, Random Structures and Algorithms, 1 (1990), 343–360 | DOI | MR | Zbl

[17] Grable B., Phelps K., Rödl V., “The minimum independence number for designs”, Combinatorica, 15 (1995), 175–185 | DOI | MR | Zbl

[18] Alon N., Spenser Dzh., Veroyatnostnyi metod, Binom, Moskva, 2007