05-39
Constructions for Normal Graphs and Some Consequences
by Wagler, A.
Preprint series: 05-39, Preprints
- MSC:
- 05C99 None of the above but in this section
Abstract: Normal graphs can be considered as weaker perfect graphs in several ways. However, only few graphs are known yet to be normal, apart from perfect graphs, odd holes, and odd antiholes of length at least 9. Körner and de Simone conjectured 1999 that every graph without a 5-hole, 7-hole, and 7-antihole is normal. As there exist normal graphs containing these three subgraphs, it is worth to look for other ways to construct or detect normal graphs. For that, we treat the behavior of normal graphs under certain construction techniques (substitution, composition, and clique identification), providing several ways to construct new normal graphs from normal and even not normal ones, and consider the corresponding structural decompositions (homogeneous sets, skew partitions, and clique cutsets). Our results imply that normal graphs cannot be characterized by means of decomposition techniques as well as by forbidden subgraphs. We address negative consequences for the algorithmic behavior of normal graphs, reflected by the fact that neither the imperfection ratio can be bounded for normal graphs nor a chi-binding function exists. The latter is even true for the class of graphs without 5-holes, 7-holes, and 7-antiholes. We conclude that normal graphs are indeed only `normal\'.
Keywords: normal graphs, graph composition techniques
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.