The chromatic numbers of graph bundles over cycles. (English) Zbl 0818.05035

Authors’ abstract: Graph bundles generalize the notions of covering graphs and products of graphs. The chromatic numbers of product bundles with respect to the Cartesian, the strong and the tensor product whose base and fiber are cycles are determined.
Reviewer: S.Stahl (Lawrence)


05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles


Zbl 0815.05029
Full Text: DOI


[1] Biggs, N. L., Discrete Mathematics (1989), Clarendon Press: Clarendon Press Oxford · Zbl 0682.05001
[2] Geller, D., r-tuple colorings of uniquely colorable graphs, Discrete Math., 16, 9-12 (1976) · Zbl 0338.05104
[3] Geller, D.; Stahl, S., The chromatic number and other parameters of the lexicographic product, J. Combin. Theory Ser. B, 19, 87-95 (1975) · Zbl 0282.05114
[4] Hedetniemi, S., Homomorphisms of graphs and automata, (Tech. Report 03105-44-T (1966), University of Michigan) · Zbl 0297.05120
[5] Husemoller, D., Fibre Bundles (1966), McGraw-Hill: McGraw-Hill New York · Zbl 0144.44804
[6] Klavẑar, S., Two remarks on retracts of graph products, Discrete Math., 109, 155-160 (1992) · Zbl 0780.05055
[7] Klavẑar, S., Strong products of χ-critical graphs, Acquationes Math., 45, 153-162 (1993) · Zbl 0787.05039
[8] Klavẑar, S.; Mohar, B., Coloring graph bundles, J. Graph Theory, 18 (1995), to appear · Zbl 0815.05029
[9] Kwak, J. H.; Lee, J., Isomorphism classes of graph bundles, Canad. J. Math., 42, 747-761 (1990) · Zbl 0739.05042
[10] Mohar, B.; Pisanski, T.; Ŝkoviera, M., The maximum genus of graph bundles, European J. Combin., 9, 215-224 (1988) · Zbl 0642.05019
[11] Pisanski, T.; Shawe-Taylor, J.; Vrabec, J., Edge-colorability of graph bundles, J. Combin. Theory Ser. B, 35, 12-19 (1983) · Zbl 0505.05034
[12] Pisanski, T.; Vrabec, J., Graph bundles (1982), unpublished manuscript
[13] Sabidussi, G., Graphs with given group and given graph-theoretical properties, Canad. J. Math., 9, 515-525 (1957) · Zbl 0079.39202
[14] Stahl, S., \(n\)-tuple colorings and associated graphs, J. Combin. Theory Ser. B, 20, 185-203 (1976) · Zbl 0293.05115
[15] Vesztergombi, K., Some remarks on the chromatic number of the strong product of graphs, Acta Cybernet., 4, 207-212 (1978/79) · Zbl 0397.05025
[16] Vesztergombi, K., Chromatic number of strong product of graphs, (Lovász, L.; Sós, V. T., Algebraic Methods in Graph Theory. Algebraic Methods in Graph Theory, Colloq. Math. Soc. J. Bolyai, Vol. 25 (1982), North-Holland: North-Holland Amsterdam), 819-825 · Zbl 0472.05023
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.