Hypergraph colouring

doi:10.1017/CBO9781139519793.014

11 - Hypergraph colouring

Published online by Cambridge University Press: 05 May 2015

Csilla Bujtás ,

Zsolt Tuza and

Vitaly Voloshin

Edited by

Lowell W. Beineke and

Robin J. Wilson

Show author details

Csilla Bujtás: Affiliation:
University of Pannonia
Zsolt Tuza: Affiliation:
University of Pannonia
Vitaly Voloshin: Affiliation:
Troy University
Lowell W. Beineke: Affiliation:
Purdue University, Indiana
Robin J. Wilson: Affiliation:
The Open University, Milton Keynes

Book contents

Get access

Summary

We discuss the colouring theory of finite set systems. This is not merely an extension of results from collections of 2-element sets (graphs) to larger sets. The wider structure (hypergraphs) offers many interesting new kinds of problems, which either have no analogues in graph theory or become trivial when we restrict them to graphs.

Introduction

In this introductory section we give the most important definitions required to study hypergraph colouring, and briefly survey the half-century history of this topic. For more details on the material of Sections 1 and 2 we refer to Berge [8], Zykov [76] and Duchet [27].

Let V = {v1, v2, …, vn} be a finite set of elements called vertices, and let ℇ = {E1, E2, …, Em} be a family of subsets of V called edges or hyperedges. The pair ℌ = (V, ℇ) is called a hypergraph with vertex-set V = V(ℌ) and edge-set ℇ = ℇ(ℌ). The hypergraph ℌ = (V, ℇ) is sometimes called a set system. If each edge of a hypergraph contains precisely two vertices, then it is a graph. As in graph theory, the number |V| = n is called the order of the hypergraph. Edges with fewer than two elements are usually allowed, but will be disregarded here. Thus, throughout this chapter we assume that each edge E ∈ ℇ contains at least two vertices, unless stated explicitly otherwise. Edges that coincide are called multiple edges.

In a hypergraph, two vertices are said to be adjacent if there is an edge containing both of these vertices. The adjacent vertices are sometimes called neighbours of each other, and the set of neighbours of a given vertex v is called the (open) neighbourhood N(v) of v. If v ∈ E, then the vertex v and the edge E are incident with each other. For an edge E, the number |E| is called the size or cardinality of E.

Type: Chapter
Information: Topics in Chromatic Graph Theory , pp. 230 - 254

DOI: https://doi.org/10.1017/CBO9781139519793.014 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2015

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. N., Alon and Z., Bregman, Every 8-uniform 8-regular hypergraph is 2-colorable, Graphs Combin. 4 (1988), 303–306.Google Scholar

2. G., Bacsό, Cs., Bujtás, Zs., Tuza and V., Voloshin, New challenges in the theory of hypergraph coloring, Advances in Discrete Mathematics and Applications, RMS Lecture Notes 13 (2010), 45–57.Google Scholar

3. G., Bacsό, T., Héger and T., Szőnyi, The 2-blocking number and the upper chromatic number of PG(2, q), J. Combin. Designs 21 (2013), 585–602.Google Scholar

4. G., Bacso and Zs., Tuza, Upper chromatic number of finite projective planes, J. Combin. Designs 16 (2008), 221–230.Google Scholar

5. G., Bacsó, Zs., Tuza and V., Voloshin, Unique colorings of bi-hypergraphs, Austral. J. Combin. 27 (2003), 33–45.Google Scholar

6. Zs., Baranyai, On the factorization of the complete uniform hypergraph, Infinite and Finite Sets (Keszthely, 1973) (eds. A., Hajnal, R., Rado and V. T., Sós), Colloq. Math. Soc. J. Bolyai 10, North-Holland (1975), 91–107.

7. C., Berge, Sur certains hypergraphes généralisant les graphes bipartites, Combinatorial Theory and its Applications, I (Balatonfüred, 1969), North-Holland (1970), 119–133.Google Scholar

8. C., Berge, Hypergraphs: Combinatorics of Finite Sets, North-Holland, 1989.Google Scholar

9. C., Berge, Motivations and history of some of my conjectures, Discrete Math. 165/166 (1997), 61–70.Google Scholar

10. G. D., Birkhoff, A determinant formula for the number of ways of colouring a map, Ann. of Math. 14 (1912), 42–46.Google Scholar

11. Cs., Bujtás, E., Sampathkumar, Zs., Tuza, L., Pushpalatha and R. C., Vasundhara, Improper C-colorings of graphs, Discrete Applied Math. 159 (2011), 174–186.Google Scholar

12. Cs., Bujtás and Zs., Tuza, Orderings of uniquely colorable mixed hypergraphs, Discrete Applied Math. 155 (2007), 1395–1407.Google Scholar

13. Cs., Bujtás and Zs., Tuza, Color-bounded hypergraphs, III: Model comparison, Applic. Anal. and Discrete Math. 1 (2007), 36–55.Google Scholar

14. Cs., Bujtás and Zs., Tuza, Uniform mixed hypergraphs: The possible numbers of colors, Graphs Combin. 24 (2008), 1–12.Google Scholar

15. Cs., Bujtás and Zs., Tuza, Color-bounded hypergraphs, I: General results, Discrete Math. 309 (2009), 4890–4902.Google Scholar

16. Cs., Bujtás and Zs., Tuza, Color-bounded hypergraphs, II: Interval hypergraphs and hypertrees, Discrete Math. 309 (2009), 6391–6401.Google Scholar

17. Cs., Bujtás and Zs., Tuza, Smallest set-transversals of k-partitions, Graphs Combin. 25 (2009), 807–816.Google Scholar

18. Cs., Bujtás and Zs., Tuza, C-perfect hypergraphs, J. Graph Theory 64 (2010), 132–149.Google Scholar

19. Cs., Bujtás and Zs., Tuza, Voloshin's conjecture for C-perfect hypertrees, Australas. J. Combin. 48 (2010), 253–267.Google Scholar

20. Cs., Bujtás and Zs., Tuza, Maximum number of colors: C-coloring and related problems, J. Geometry 101 (2011), 83–97.Google Scholar

21. Cs., Bujtás and Zs., Tuza, Color-bounded hypergraphs, VI: Structural and functional jumps in complexity, Discrete Math. 313 (2013), 1965–1977.Google Scholar

22. Cs., Bujtás and Zs., Tuza, Approximability of the upper chromatic number of hypergraphs, manuscript, 2013.

23. E., Bulgaru and V., Voloshin, Mixed interval hypergraphs, Discrete Applied Math. 77 (1997), 24–41.Google Scholar

24. D., Défossez, A sufficient condition for the bicolorability of a hypergraph, Discrete Math. 308 (2008), 2265–2268.Google Scholar

25. K., Diao, G., Liu, D., Rautenbach and P., Zhao, A note on the least number of edges of 3-uniform hypergraphs with upper chromatic number 2, Discrete Math. 306 (2006), 670–672.Google Scholar

26. E., Drgas-Burchardt and E., Łazuka, Chromatic polynomials of hypergraphs, Applied Math. Letters 20 (2007), 1250–1254.Google Scholar

27. P., Duchet, Hypergraphs, Handbook of Combinatorics, Vol. 1 (eds. R. L., Graham, M., Grotschel and L., Lovasz), Elsevier (1995), 381–432.Google Scholar

28. Z., Dvořák, J., Král, D.O., Král' Pangrác, Pattern hypergraphs, Electron. J. Combin. 17 (2010), #R15.Google Scholar

29. P., Erdős, On a combinatorial problem, Nordisk Mat. Tidskr. 11 (1963), 5–10.Google Scholar

30. P., Erdős, On a combinatorial problem II, Acta Math. Acad. Sci. Hungar. 15 (1964), 445–447.Google Scholar

31. P., Erdős and A., Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61–99.Google Scholar

32. P., Erdős and L., Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, Infinite and Finite Sets (Keszthely, 1973) (eds. A., Hajnal, R., Rado and V. T., Sos), Colloq. Math. Soc. J. Bolyai 10, North-Holland (1975), 609–627.Google Scholar

33. J.-C., Fournier and M., Las Vergnas, Une class d'hypergraphes bichromatiques, Discrete Math. 2 (1972), 407–410.Google Scholar

34. T., Gallai, On directed paths and circuits, Theory of Graphs (Tihany, 1966) (eds. P., Erdős and G. O. H., Katona), Academic Press, San Diego (1968), 115–118.Google Scholar

35. M., Hegyháti and Zs., Tuza, Colorability of mixed hypergraphs and their chromatic inversions, J. Combin. Optim. 25 (2013), 737–751.Google Scholar

36. M. A., Henning and A., Yeo, 2-colorings in k-regular k-uniform hypergraphs, Europ. J. Combin. 34 (2013), 1192–1202.Google Scholar

37. A., Jaffe, T., Moscibroda and S., Sen, On the price of equivocation in Byzantine agreement, Proc. 2012 ACM Symp. on Principles of Distributed Computing, ACM, New York (2012), 309–318.Google Scholar

38. T., Jiang, D., Mubayi, V., Voloshin, Zs., Tuza and D., West, The chromatic spectrum of mixed hypergraphs, Graphs Combin. 18 (2002), 309–318.Google Scholar

39. D., Kobler and A., Kündgen, Gaps in the chromatic spectrum of face-constrained plane graphs, Electron. J. Combin. 8 (2001), #N3.Google Scholar

40. A. V., Kostochka and M., Stiebitz, On the number of edges in colour-critical graphs and hypergraphs, Combinatorica 20 (2000), 521–530.Google Scholar

41. D., Kral', A counter-example to Voloshin's hypergraph co-perfectness conjecture, Australas. J. Combin. 27 (2003), 25–41.Google Scholar

42. D., Kral', On feasible sets of mixed hypergraphs, Electron. J. Combin. 11 (2004), #R19.Google Scholar

43. D.J., Král' Kratochvíl, A., Proskurowski and H.-J., Voss, Coloring mixed hypertrees, Discrete Applied Math. 154 (2006), 660–672.Google Scholar

44. D.J., Král' Kratochvíl and H.-J., Voss, Mixed hypercacti, Discrete Math. 286 (2004), 99–113.Google Scholar

45. L., Lovász, On chromatic number of finite set-systems, Acta Math. Acad. Sci. Hungar. 19 (1968), 59–67.Google Scholar

46. L., Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972), 253–267.Google Scholar

47. L., Lovász, Coverings and colourings of hypergraphs, Congr. Numer. 8 (1973), 3–12.Google Scholar

48. P., Mihók, Zs., Tuza and M., Voigt, Fractional P-colourings and P-choice-ratio, Tatra Mountains Math. Publ. 18 (1999), 69–77.Google Scholar

49. L., Milazzo and Zs., Tuza, Upper chromatic number of Steiner triple and quadruple systems, Discrete Math. 174 (1997), 247–259.Google Scholar

50. L., Milazzo and Zs., Tuza, Logarithmic upper bound for the upper chromatic number of S(t, t + 1, v) systems, Ars Combin. 92 (2009), 213–223.Google Scholar

51. L., Milazzo, Zs., Tuza and V. I., Voloshin, Strict colorings of Steiner triple and quadruple systems: a survey, Discrete Math. 261 (2003), 399–411.Google Scholar

52. J., Nešetřil and V., Rodl, A short proof of the existence of highly chromatic hypergraphs without short cycles, J. Combin. Theory (B) 27 (1979), 225–227.Google Scholar

53. A., Niculitsa and V., Voloshin, About uniquely colorable mixed hypertrees, Discuss. Math. Graph Theory 20 (2000), 81–91.Google Scholar

54. A., Niculitsa and H.-J., Voss, A characterization of uniquely colorable mixed hypergraphs of order n with upper chromatic numbers n − 1and n − 2, Australas. J. Combin. 21 (2000), 167–177.Google Scholar

55. K. T., Phelps and V., Rodl, On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems, Combinatorica 4 (1984), 79–88.Google Scholar

56. J., Radhakrishnan and A., Srinivasan, Improved bounds and algorithms for hypergraph 2-coloring, Random Struct. Alg. 16 (2000), 4–32.Google Scholar

57. B., Roy, Nombre chromatique et plus longs chemins d'un graphe, Rev. AFIRO 1 (1967), 127–132.Google Scholar

58. P. D., Seymour, On the two-colouring of hypergraphs, Quart. J. Math. Oxford (3) 25 (1974), 303–312.Google Scholar

59. F., Sterboul, A new combinatorial parameter, Infinite and Finite Sets (Keszthely, 1973) (eds. A., Hajnal, R., Rado and V. T., Sos), Colloq. Math. Soc. J. Bolyai 10, North-Holland (1975), 1387–1404.Google Scholar

60. F., Sterboul, Un problème extremal pour les graphes et les hypergraphes, Discrete Math. 11 (1975), 71–78.Google Scholar

61. I., Tomescu, Sure le probléme du coloriage des graphes généralisés, C. R. Acad. Sci. (Paris) 267:6 (1968), 250–252.Google Scholar

62. Zs., Tuza, Graph coloring in linear time, J. Combin. Theory (B) 55 (1992), 236–243.Google Scholar

63. Zs., Tuza and V., Voloshin: Uncolorable mixed hypergraphs, Discrete Applied Math. 99 (2000), 209–227.Google Scholar

64. Zs., Tuza and V., Voloshin, Problems and results on colorings of mixed hypergraphs, Horizons of Combinatorics (eds. E., Gyciri, G., Katona and L., Lovasz), Bolyai Society Math. Studies 17, Springer-Verlag (2008), 235–255.Google Scholar

65. Zs., Tuza, V. I., Voloshin and H., Zhou, Uniquely colorable mixed hypergraphs, Discrete Math. 248 (2002), 221–236.Google Scholar

66. V. I., Voloshin, The mixed hypergraphs, Computer Sci. J. Moldova 1 (1993), 45–52.Google Scholar

67. V. I., Voloshin, On the upper chromatic number of a hypergraph, Australas. J. Combin. 11 (1995), 25–45.Google Scholar

68. V. I., Voloshin, Coloring Mixed Hypergraphs: Theory, Algorithms and Applications, Fields Institute Monographs 17, Amer. Math. Soc., 2002.Google Scholar

69. V., Voloshin, Mixed Hypergraph Coloring Web Site, http://spectrum.troy.edu/voloshin/mh.html.

70. V., Voloshin and H.-J., Voss, Circular mixed hypergraphs I: colorability and unique colorability, Congr. Numer. 144 (2000), 207–219.Google Scholar

71. D. J. A., Welsh and M. B., Powell, An upper bound for the chromatic number of a graph and its application to timetabling problems, Comp. J. 10 (1967), 85–86.Google Scholar

72. H., Whitney, The colouring of graphs, Ann. of Math. 33 (1932), 688–718.Google Scholar

73. D. R., Woodall, Property B and the four-colour problem, Combinatorics, Proc. 1972 Oxford Combinatorial Conference (eds. D. J. A., Welsh and D. R., Woodall), Inst. Math. Appl. (1972), 322–340.Google Scholar

74. P., Zhao, K., Diao and K., Wang, The smallest one-realization of a given set, Electron. J. Combin. 19 (2012), #P19.Google Scholar

75. P., Zhao, K., Diao and K., Wang, The smallest one-realization of a given set, II, Discrete Math. 312 (2012), 2946–2951.Google Scholar

76. A. A., Zykov, Hypergraphs, Uspekhi Mat. Nauk 29 (1974), 89–154 (in Russian).Google Scholar

Book contents

11 - Hypergraph colouring

Summary

Access options

References

Save book to Kindle

Save book to Dropbox

Save book to Google Drive