@misc{TuzaWagler1997, author = {Tuza, Zsolt and Wagler, Annegret}, title = {Minimally non-preperfect graphs of small maximum degree}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2971}, number = {SC-97-28}, year = {1997}, abstract = {A graph \$G\$ is called preperfect if each induced subgraph \$G' \subseteq G\$ of order at least 2 has two vertices \$x,y\$ such that either all maximum cliques of \$G'\$ containing \$x\$ contain \$y\$, or all maximum indepentent sets of \$G'\$ containing \$y\$ contain \$x\$, too. Giving a partial answer to a problem of Hammer and Maffray [Combinatorica 13 (1993), 199-208], we describe new classes of minimally non-preperfect graphs, and prove the following characterizations: \begin{itemize} \item[(i)] A graph of maximum degree 4 is minimally non-preperfect if and only if it is an odd cycle of length at least 5, or the complement of a cycle of length 7, or the line graph of a 3-regular 3-connected bipartite graph. \item[(ii)] If a graph \$G\$ is not an odd cycle and has no isolated vertices, then its line graph is minimally non-preperfect if and only if \$G\$ is bipartite, 3-edge-connected, regular of degree \$d\$ for some \$d \ge 3\$, and contains no 3-edge-connected \$d'\$-regular subgraph for any \$3 \le d' \le d\$. \end{itemize}}, language = {en} }