×

Embeddings of a graph into a surface with different weak chromatic numbers. (English) Zbl 1459.05212

Summary: A weak coloring of a graph \(G\) embedded on a surface is a vertex coloring of \(G\) such that no face is monochromatic. The weak chromatic number of \(G\) is the minimum number \(k\) such that \(G\) has a weak \(k\)-coloring. A. Kündgen and R. Ramamurthi [J. Comb. Theory, Ser. B 85, No. 2, 307–337 (2002; Zbl 1029.05057)] conjectured that for each positive integer \(k\), there is a graph that has two different embeddings on the same surface whose weak chromatic numbers differ by at least \(k\). In this paper, we answer this conjecture affirmatively in two ways.

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 1029.05057
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arocha, JL; Bracho, J.; Neumann-Lara, V., Tight and untight triangulations of surfaces by complete graphs, J. Combin. Theory Ser. B, 63, 185-199 (1995) · Zbl 0832.05035 · doi:10.1006/jctb.1995.1015
[2] De Brandes, M.; Phelps, KT; Rödl, V., Coloring steiner triple systems, SIAM J. Algebr. Discret. Methods, 3, 241-249 (1982) · Zbl 0501.05036 · doi:10.1137/0603023
[3] Czap, J.; Jendrol’, S., Facially-constrained colorings of plane graphs: a survey, Discret. Math., 340, 2691-2703 (2017) · Zbl 1369.05071 · doi:10.1016/j.disc.2016.07.026
[4] Dvořák, Z.; Král’, D.; Škrekovski, R., Coloring face hypergraphs on surfaces, Eur. J. Combin., 26, 95-110 (2005) · Zbl 1067.05024 · doi:10.1016/j.ejc.2004.01.003
[5] Gross, JL; Tucker, TW, Topological graph theory (1987), New York: Wiley, New York · Zbl 0621.05013
[6] Kündgen, A.; Ramamurthi, R., Coloring face-hypergraphs of graphs on surfaces, J. Combin. Theory Ser. B, 85, 307-337 (2002) · Zbl 1029.05057 · doi:10.1006/jctb.2001.2107
[7] Mohar, B.; Thomassen, C., Graphs on surfaces (2001), Baltimore: The Johns Hopskins University Press, Baltimore · Zbl 0979.05002
[8] Nakamoto, A.; Noguchi, K.; Ozeki, K., Spanning bipartite quadrangulations of even triangulations, J. Graph Theory, 90, 267-287 (2019) · Zbl 1433.05088 · doi:10.1002/jgt.22400
[9] Negami, S.; Midorikawa, T., Loosely-tightness of triangulations of closed surface, Sci. Rep. Yokohama Nat. Univ. Sect. I Math. Phys. Chem., 43, 25-41 (1996)
[10] Negami, S., Uniqueness and faithfulness of embedding of toroidal graphs, Discret. Math., 44, 161-180 (1983) · Zbl 0508.05033 · doi:10.1016/0012-365X(83)90057-2
[11] Negami, S., Looseness ranges of triangulations on closed surface, Discret. Math., 303, 167-174 (2005) · Zbl 1084.05023 · doi:10.1016/j.disc.2005.01.010
[12] Ramamurthi, R.; West, DB, Maximum face-constrained colorings of plane graphs, Discret. Math., 274, 233-240 (2004) · Zbl 1032.05050 · doi:10.1016/j.disc.2003.09.001
[13] Ringel, G., Map color theorem (1974), Berlin: Springer, Berlin · Zbl 0287.05102 · doi:10.1007/978-3-642-65759-7
[14] Sun, T., A simple construction for orientable triangular embeddings of the complete graphs on 12s vertices, Discret. Math., 342, 1147-1151 (2019) · Zbl 1405.05041 · doi:10.1016/j.disc.2018.12.023
[15] Xuong, NH, How to determine the maximum genus of a graph, J. Combin. Theory Ser. B, 26, 217-225 (1979) · Zbl 0403.05035 · doi:10.1016/0095-8956(79)90058-3
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.