• English
    • Deutsch
  • English 
    • English
    • Deutsch
  • Login
View Item 
  •   Home
  • Universität Ulm
  • Publikationen
  • View Item
  •   Home
  • Universität Ulm
  • Publikationen
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Covers have structure

Thumbnail
vts_6486_8802.pdf (400.9Kb)
26 Seiten
Veröffentlichung
2008-07-22
Authors
Wunderlich, Henning
Arbeitspapier


Faculties
Fakultät für Ingenieurwissenschaften und Informatik
Series
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 2008
Subject 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
License
Standard (Fassung vom 03.05.2003)
https://oparu.uni-ulm.de/xmlui/license_v1

Metadata
Show full item record

DOI & 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 >



Policy | kiz service OPARU | Contact Us
Impressum | Privacy statement
 

 

Advanced Search

Browse

All of OPARUCommunities & CollectionsPersonsInstitutionsPublication typesUlm SerialsDewey Decimal ClassesEU projects UlmDFG projects UlmOther projects Ulm

My Account

LoginRegister

Statistics

View Usage Statistics

Policy | kiz service OPARU | Contact Us
Impressum | Privacy statement