Recognizing Cartesian graph bundles. (English) Zbl 0876.05094

Graph bundles are extensions of covering graphs and graph products. The authors develop an algorithm that finds a representation as a nontrivial Cartesian graph bundle for all graphs that are Cartesian graph bundles over a triangle-free simple base. The problem of recognizing graph bundles over general base remains open.
Reviewer: G.Gutin (Odense)


05C99 Graph theory
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] Aurenhammer, F.; Hagauer, J.; Imrich, W., Cartesian graph factorization at logarithmic cost per edge, Comput. Complexity, 2, 331-349 (1992) · Zbl 0770.68064
[2] Feder, T., Product graph representations, J. Graph Theory, 16, 467-488 (1992) · Zbl 0766.05092
[3] Feigenbaum, J.; Hershberger, J.; Schäffer, A. A., A polynomial time algorithm for finding the prime factors of Cartesian-product graphs, Discrete Appl. Math., 12, 123-138 (1985) · Zbl 0579.68028
[4] Graham, R. L.; Winkler, P. M., On isometric embeddings of graphs, Trans. Amer. Math. Soc., 288, 527-536 (1985) · Zbl 0576.05017
[5] Hagauer, J.; Imrich, W.; Klavzar, S., Recognizing graphs of windex 2 (1993), preprint
[6] Imrich, W., Embedding graphs into Cartesian products, graph theory and applications: East and West, Ann. New York Acad. Sci., 576, 266-274 (1989) · Zbl 0792.05044
[7] Imrich, W.; Ẑerovnik, J., Factoring Cartesian-product graphs, J. Graph Theory, 18, 557-567 (1994) · Zbl 0811.05054
[8] Klavźar, S.; Mohar, B., Coloring graph bundles, J. Graph Theory, 19, 145-155 (1995) · Zbl 0815.05029
[9] Klavźar, S.; Mohar, B., The chromatic numbers of graph bundles over cycles, Discrete Math., 138, 301-314 (1995) · Zbl 0818.05035
[10] Kwak, J. H.; Lee, J., Isomorphism classes of graph bundles, Canadian J. Math., 42, 747-761 (1990) · Zbl 0739.05042
[11] Mohar, B.; Pisanski, T.; Škoveira, M., The maximum genus of graph bundles, European J. Combin., 9, 301-314 (1988)
[12] Pisanski, T.; Shawe-Taylor, J.; Vrabec, J., Edge-colorability of graph bundles, J. Combin. Theory Ser. B, 35, 12-19 (1983) · Zbl 0505.05034
[13] Pisanski, T.; Vrabec, J., Graph bundles (1982), unpublished manuscript
[14] Sabidussi, G., Graph multiplication, Math. Z., 72, 446-457 (1960) · Zbl 0093.37603
[15] (Pisanski, T., Vega Version 0.2: Quick Reference Manual and Vega Graph Gallery (1995), IMFM: IMFM Ljubljana)
[16] Winkler, P. M., Factoring a graph in polynomial time, European J. Combin., 8, 209-212 (1987) · Zbl 0625.05050
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.