Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-kw2vx Total loading time: 0 Render date: 2025-01-13T18:14:29.907Z Has data issue: false hasContentIssue false

11 - Hypergraph colouring

Published online by Cambridge University Press:  05 May 2015

By
Csilla Bujtás ,
Zsolt Tuza  and
Vitaly Voloshin
Edited by
Lowell W. Beineke  and
Robin J. Wilson
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
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
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

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×