On cover-structure graphs |
| |
Authors: | Henning Wunderlich |
| |
Institution: | aUniversität Ulm, Fakultät für Ingenieurwissenschaften und Informatik, Institut für Theoretische Informatik, Oberer Eselsberg, 89069 Ulm, Germany |
| |
Abstract: | Motivated by a problem in communication complexity, we study cover-structure graphs (cs-graphs), defined as intersection graphs of maximal monochromatic rectangles in a matrix. We show that not every graph is a cs-graph. Especially, squares and odd holes are not cs-graphs.It is natural to look at graphs (beautiful graphs) having the property that each induced subgraph is a cs-graph. They form a new class of Berge graphs. We make progress towards their characterization by showing that every square-free bipartite graph is beautiful, and that beautiful line graphs of square-free bipartite graphs are just Path-or-Even-Cycle-of-Cliques graphs. |
| |
Keywords: | Perfect graphs Berge graphs Beautiful graphs Information theory Communication complexity Rectangle covers |
本文献已被 ScienceDirect 等数据库收录! |
|