Previous |  Up |  Next


Title: An application of principal bundles to coloring of graphs and hypergraphs (English)
Author: Milgram, James R.
Author: Zvengrowski, Peter
Language: English
Journal: Proceedings of the Winter School "Geometry and Physics"
Issue: 1993
Pages: [161]-167
Category: math
Summary: An interesting connection between the chromatic number of a graph $G$ and the connectivity of an associated simplicial complex $N(G)$, its ``neighborhood complex'', was found by Lov\'asz in 1978 (cf. {\it L. Lov\'asz} [J. Comb. Theory, Ser. A 25, 319-324 (1978; Zbl 0418.05028)]). In 1986 a generalization to the chromatic number of a $k$-uniform hypergraph $H$, for $k$ an odd prime, using an associated simplicial complex $C(H)$, was found ([{\it N. Alon}, {\it P. Frankl} and {\it L. Lov\'asz}, Trans. Am. Math. Soc. 298, 359-370 (1986; Zbl 0605.05033)], Prop. 2.1). It was already noted in the above mentioned papers that there is an action of $Z/2$ on $N(G)$, and of $Z/k$ on $C(H)$, for any graph $G$ and any $k$-uniform hypergraph $H$, $k \ge 2$ (a 2-uniform hypergraph is just a graph). In this note we take advantage of this action to construct an associated principal $(Z/k)$-bundle $\xi$, and state theorems relating the chromatic number of the graph or hypergraph to! (English)
MSC: 05C10
MSC: 05C15
MSC: 05C65
MSC: 55R10
MSC: 55R99
idZBL: Zbl 0831.05030
idMR: MR1344009
Date available: 2009-07-13T21:33:38Z
Last updated: 2012-09-18
Stable URL:


Files Size Format View
WSGP_13-1993-1_16.pdf 311.0Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo