Covers have structure
Arbeitspapier
Faculties
Fakultät für Ingenieurwissenschaften und InformatikSeries
Ulmer Informatik-Berichte
Abstract
We establish a new connection between the theory of Berge graphs (perfect graphs) and communication complexity. We discover a new class of square-free Berge graphs, the class of beautiful graphs, and make progress towards their characterization: On the one hand, we give a complete list of forbidden induced subgraphs of order $\leq 7$, on the other hand, we show that every square-free bipartite graph is beautiful, and, as the main result, we characterize the beautiful line graphs of square-free bipartite graphs.
Date created
2008
Original publication
Ulmer Informatik-Berichte, Nr. 2008-08, Juli 2008Subject headings
[GND]: Bipartiter Graph | Perfekter Graph[LCSH]: Perfect graphs
[Free subject headings]: Berge graphs | Communication complexity
[DDC subject group]: DDC 004 / Data processing & computer science
Metadata
Show full item recordDOI & citation
Please use this identifier to cite or link to this item: http://dx.doi.org/10.18725/OPARU-1002
Wunderlich, Henning (2008): Covers have structure. Open Access Repositorium der Universität Ulm und Technischen Hochschule Ulm. http://dx.doi.org/10.18725/OPARU-1002
Citation formatter >