hal-00005638, version 1
The Reduced Genus of a Multigraph
STACS 99 (1999) 16-31
Résumé : We define here the reduced genus of a multigraph as the minimum genus of a hypergraph having the same adjacencies with the same multiplicities. Through a study of embedded hypergraphs, we obtain new bounds on the coloring number, clique number and point arboricity of simple graphs of a given reduced genus. We present some new related problems on graph coloring and graph representation.
- 1 :
- CNRS : UMR8557 – École des Hautes Études en Sciences Sociales [EHESS]
- Domaine : Mathématiques/Combinatoire
- hal-00005638, version 1
- http://hal.archives-ouvertes.fr/hal-00005638
- oai:hal.archives-ouvertes.fr:hal-00005638
- Contributeur :
- Soumis le : Lundi 27 Juin 2005, 00:17:39
- Dernière modification le : Lundi 27 Juin 2005, 00:17:39
Exporter