×

zbMATH — the first resource for mathematics

Coloring face-hypergraphs of graphs on surfaces. (English) Zbl 1029.05057
Authors’ abstract: The face-hypergraph, \({\mathcal H}(G)\), of a graph \(G\) embedded in a surface has vertex set \(V(G)\), and every face of \(G\) corresponds to an edge of \({\mathcal H}(G)\) consisting of the vertices incident to the face. We study coloring parameters of these embedded hypergraphs. A hypergraph is \(k\)-colorable (\(k\)-choosable) if there is a coloring of its vertices from a set of \(k\) colors (from every assignment of lists of size \(k\) to its vertices) such that no edge is monochromatic. Thus a proper coloring of a face-hypergraph corresponds to a vertex coloring of the underlying graph such that no face is monochromatic. We show that hypergraphs can be extended to face-hypergraphs in a natural way and use tools from topological graph theory, the theory of hypergraphs, and design theory to obtain general bounds for the coloring and choosability problems. To show the sharpness of several bounds, we construct for every even \(n\) an \(n\)-vertex pseudo-triangulation of a surface such that every triple is a face exactly once. We provide supporting evidence for our conjecture that every plane face-hypergraph is \(2\)-choosable and we pose several open questions, most notably: Can the vertices of a planar graph always be properly colored from lists of size 4, with the restriction on the lists that the colors come in pairs and a color is in a list if and only if its twin color is? An affirmative answer to this question would imply our conjecture, as well as the four color theorem and several open problems.

MSC:
05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albertson, M.; Grossman, S.; Haas, R., Partial List colorings, Discrete math., 214, 235-240, (2000) · Zbl 0957.05037
[2] Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134, (1992) · Zbl 0756.05049
[3] Alon, N.; Spencer, J., The probabilistic method, Wiley – interscience series in discrete math and optimization, (1992), Wiley New York
[4] Appel, K.; Haken, W., Every planar map is four-colorable, Illinois J. math., 21, 429-567, (1977) · Zbl 0387.05009
[5] Berge, C., Graphs and hypergraphs, (1973), North-Holland Amsterdam/London · Zbl 0483.05029
[6] Berge, C., Hypergraphs, (1989), North-Holland Amsterdam/New York
[7] Böhme, T.; Mohar, B.; Stiebitz, M., Dirac’s map-color theorem for choosability, J. graph theory, 32, 327-339, (1999) · Zbl 0941.05025
[8] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), Amer. Elsevier New York
[9] Bonnington, C.P.; Grannell, M.J.; Griggs, T.S.; Širáň, J., Exponential families of non-isomorphic triangulations of complete graphs, J. combin. theory ser. B, 78, 169-184, (2000) · Zbl 1023.05041
[10] de Brandes, M.; Phelps, K.T.; Rödl, V., Coloring Steiner triple systems, SIAM J. algebraic discrete methods, 3, 241-249, (1982) · Zbl 0501.05036
[11] Burstein, M.I., An upper bound for the chromatic number of hypergraphs, Sakharth. SSR mecn. akad. moambe, 75, 37-40, (1974)
[12] G. G. Chappell, personal communication.
[13] Colbourn, C.J.; Colbourn, M.J.; Phelps, K.T.; Rödl, V., Coloring block designs is NP-complete, SIAM J. algebraic discrete methods, 3, 305-307, (1982) · Zbl 0497.05022
[14] Colbourn, C.J.; Rosa, A., Triple systems, (1999), Oxford Univ. Press London · Zbl 0607.05014
[15] Erdős, P.; Hajnal, A., On chromatic number of graphs and set-systems, Acta math. acad. sci. hungar., 17, 61-99, (1966) · Zbl 0151.33701
[16] Erdős, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, Proceedings of the west coast conference on combinatorics, graph theory and computing, (1979), Humboldt State Univ Arcata, p. 125-157
[17] Fisk, S.; Mohar, B., Coloring graphs without short non-bounding cycles, J. combin. theory ser. B, 60, 268-276, (1994) · Zbl 0793.05058
[18] Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), Freeman San Francisco · Zbl 0411.68039
[19] Grannell, M.J.; Griggs, T.S.; Širáň, J., Face 2-colourable triangular embeddings of complete graphs, J. combin. theory ser. B, 74, 8-19, (1998) · Zbl 0914.05019
[20] Grannell, M.J.; Griggs, T.S.; Širáň, J., Surface embeddings of Steiner triple systems, J. combin. des., 6, 325-336, (1998) · Zbl 0916.05009
[21] Gross, J.L.; Tucker, T.W., Topological graph theory, (1987), Wiley New York · Zbl 0621.05013
[22] Gutner, S., The complexity of planar graph choosability, Discrete math., 159, 119-130, (1996) · Zbl 0865.05066
[23] Heawood, P.J., Map-colour theorem, Quart. J. pure appl. math., 24, 332-339, (1890) · JFM 22.0562.02
[24] Heffter, L., Über das problem der nachbargebiete, Math. ann., 38, 479-508, (1891) · JFM 23.0543.01
[25] Hoffman, P.; Richter, B., Embedding graphs in surfaces, J. combin. theory ser. B, 36, 65-84, (1984) · Zbl 0514.05028
[26] Hutchinson, J.; Richter, B.; Seymour, P., Colouring Eulerian triangulations, J. combin. theory ser. B, 84, 225-239, (2002) · Zbl 1025.05015
[27] Jungerman, M.; Stahl, S.; White, A.T., Imbeddings of hypergraphs, Congr. numer., 29, 545-557, (1980)
[28] Komlós, J.; Pintz, J.; Szemerédi, E., A lower bound for Heilbronn’s problem, J. London math. soc. (2), 25, 13-24, (1982) · Zbl 0483.52008
[29] A. V. Kostochka, personal communication.
[30] Kronk, H.V., An analogue to the heawood map-colouring problem, J. London math. soc. (2), 1, 750-752, (1969) · Zbl 0184.27603
[31] Kündgen, A.; Mendelsohn, E.; Voloshin, V., Colouring planar mixed hypergraphs, Electron. J. combin., 7, R60, (2000) · Zbl 0978.05027
[32] Lawrencenko, S.; Negami, S.; White, A.T., Three nonisomorphic triangulations of an orientable surface with the same complete graph, Discrete math., 135, 367-369, (1994) · Zbl 0823.05027
[33] L. Lovász, Graphs and set systems, in Beiträge zur Graphentheorie, Kolloquium, Manebach, 1967, pp. 99-106, Teubner, Leipzig, 1968.
[34] Mirzakhani, M., A small non-4-choosable planar graph, Bull. inst. combin. appl., 17, 15-18, (1996) · Zbl 0860.05029
[35] Mohar, B.; Seymour, P., Coloring locally bipartite graphs on surfaces, J. combin. theory ser. B, 84, 301-310, (2002) · Zbl 1079.05027
[36] Mohar, B.; Thomassen, C., Graphs on surfaces, (2001), Johns Hopkins Press Baltimore · Zbl 0979.05002
[37] Mohar, B.; Škrekovski, R., The grötzsch theorem for the hypergraph of maximal cliques, Electron. J. combin., 6, R26, (1999) · Zbl 0930.05040
[38] Negami, S., Uniqueness and faithfulness of embedding of toroidal graphs, Discrete math., 44, 161-180, (1983) · Zbl 0508.05033
[39] Penaud, J.G., Une propriété de bicoloration des hypergraphes planaires, Cahiers centre études rech. opér., 17, 345-349, (1975) · Zbl 0334.05101
[40] Phelps, K.T.; Rödl, V., On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems, Combinatorica, 4, 79-88, (1984) · Zbl 0535.68030
[41] Phelps, K.T.; Rödl, V., Steiner triple systems with minimum independence number, Ars combin., 21, 167-172, (1986) · Zbl 0625.05012
[42] Ramamurthi, R., Coloring problems on graphs and hypergraphs, (2001)
[43] Ringel, G., Map color theorem, (1974), Springer-Verlag New York/Berlin · Zbl 0287.05102
[44] Ringel, G.; Youngs, J.W.T., Solution of the heawood map-coloring problem, Proc. natl. acad. sci. U.S.A., 60, 438-445, (1968) · Zbl 0155.51201
[45] Robertson, N.; Sanders, D.; Seymour, P.; Thomas, R., A new proof of the four-colour theorem, Electron. res. announc. amer. math. soc., 2, 17-25, (1996) · Zbl 0865.05039
[46] Rosenfeld, M., The number of cycles in 2-factors of cubic graphs, Discrete math., 84, 285-294, (1990) · Zbl 0728.05051
[47] Thomassen, C., Five-coloring maps on surfaces, J. combin. theory ser. B, 59, 89-105, (1993) · Zbl 0794.05026
[48] Thomassen, C., Every planar graph is 5-choosable, J. combin. theory ser. B, 62, 180-181, (1994) · Zbl 0805.05023
[49] Thomassen, C., Embeddings and minors, Handbook of combinatorics, (1995), Elsevier Amsterdam, p. 301-349 · Zbl 0851.05043
[50] Thomassen, C., Color-critical graphs on a fixed surface, J. combin. theory ser. B, 70, 67-100, (1997) · Zbl 0883.05051
[51] Vizing, V.G., Coloring the vertices of a graph in prescribed colors, Diskret. anal., 29, 3-10, (1976) · Zbl 1249.90303
[52] Voigt, M., List colourings of planar graphs, Discrete math., 120, 215-219, (1993) · Zbl 0790.05030
[53] Walsh, T.R.S., Hypermaps versus bipartite maps, J. combin. theory ser. B, 18, 155-163, (1975) · Zbl 0302.05101
[54] D. B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, NJ, 1996, 2001. · Zbl 0845.05001
[55] Xuong, N.H., How to determine the maximum genus of a graph, J. combin. theory ser. B, 26, 217-225, (1979) · Zbl 0403.05035
[56] Zykov, A.A., Hypergraphs, Uspekhi mat. nauk, 29, 89-154, (1974) · Zbl 0311.05136
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.