The chromatic numbers of graph bundles over cycles

✍ Scribed by Sandi Klavẑar; Bojan Mohar

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 565 KB
• Volume: 138
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)00212-2

✦ Synopsis

Graph bundles generalize the notion of covering graphs and products of graphs. The chromatic numbers of product bundles with respect to the Cartesian, strong and tensor product whose base and fiber are cycles are determined.

1. Introduction

If G is a graph, V(G) and E(G) denote its vertex and edge set, respectively. The

Cartesian product G D H of graphs G and H is the graph with vertex set V(G) × V(H) and (a,x)(b,y)~E(GDH) whenever ablE(G) and x=y, or a=b and xy~E(H). The tensor product G x H of graphs G and H is the graph with vertex set V(G) x V(H) and (a,x)(b,y)~E(GxH) whenever ablE(G) and xyeE(H). The strong product G~H of graphs G and H is the graph with vertex set V(G)x V(H) and E(G []H)= E(G x H)w E(G~H).

Graph bundles [11,12] generalize the notion of covering graphs and Cartesian products of graphs. The notion follows the definition of fiber bundles and vector bundles that became standard objects in topology [5] as space which locally look hike a product. Graph bundles corresponding to arbitrary graph products were introduced in [12, 10]. We refer to [8, 10,12] for definitions and basic results.

In this paper we will only consider graph bundles over cycles. They can be represented as described below. (Here we take this description as a definition.) Let . ~ be a Cartesian, tensor, or a strong product operation. Let q, I~>3, be a cycle with consecutive vertices Vo,Vl .....