Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Marked Items 
Alerts
Order History
Saved Items
All
Favorites
    
Book Chapter Printable view
The Reduced Genus of a Multigraph

The Reduced Genus of a Multigraph

Book SeriesLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
ISSN0302-9743 (Print) 1611-3349 (Online)
VolumeVolume 1563/1999
BookSTACS 99
DOI10.1007/3-540-49116-3
Copyright1999
ISBN978-3-540-65691-3
DOI10.1007/3-540-49116-3_2
Pages16-31
Subject CollectionComputer Science
SpringerLink DateFriday, January 01, 1999
Add to marked items

The Reduced Genus of a Multigraph

Patrice Ossona de Mendez6 Contact Information

(6)  CNRS UMR 0017, E.H.E.S.S., 54 Bd Raspail, 75006 Paris, France
Abstract
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.
This work was partially supported by the Esprit LTR Project no 20244-ALCOM IT

Contact Information Patrice Ossona de Mendez
Email: pom@ehess.fr
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.
more options
Find


Export this chapter
Export this chapter as RIS | Text
 
Frequently asked questions | General information on journals and books | Send us your feedback | Impressum | Contact
© Springer. Part of Springer Science+Business Media
Privacy, Disclaimer, Terms and Conditions, © Copyright Information
Remote Address: 38.107.191.106 • Server: mpweb16
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)