An application of principal bundles to coloring of graphs and hypergraphs

Proceedings of the Winter School "Geometry and Physics", GDML_Books, (1994), p. [161]-167 / Harvested from

Résumé

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ász in 1978 (cf. L. Lovász [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 ([N. Alon, P. Frankl and L. Lovász, 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 \geq 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 $ξ$ , and state theorems relating the chromatic number of the graph or hypergraph to!

MR MR1344009 | Zbl 0831.05030

EUDML-ID : urn:eudml:doc:221367
Mots clés:

@article{701553,
     title = {An application of principal bundles to coloring of graphs and hypergraphs},
     booktitle = {Proceedings of the Winter School "Geometry and Physics"},
     series = {GDML\_Books},
     publisher = {Circolo Matematico di Palermo},
     address = {Palermo},
     year = {1994},
     pages = {[161]-167},
     mrnumber = {MR1344009},
     zbl = {0831.05030},
     url = {http://dml.mathdoc.fr/item/701553}
}

Milgram, James R.; Zvengrowski, Peter. An application of principal bundles to coloring of graphs and hypergraphs, dans Proceedings of the Winter School "Geometry and Physics", GDML_Books,  (1994), pp. [161]-167. http://gdmltest.u-ga.fr/item/701553/