THE GRAPHS WITH ALL SUBGRAPHS T-PERFECT

The richest class of t-perfect graphs known so far consists of the gra phs with no so-called odd-K-4. Clearly, these graphs have the special property that they are hereditary t-perfect in the sense that every su bgraph is also t-perfect, but they are not the only ones. In this pape r we characterize hereditary t-perfect graphs by showing that any non- t-perfect graph contains a non-perfect subdivision of K-4, called a ba d-K-4. To prove the result we show which ''weakly 3-connected'' graphs contain no bad-K-4; as a side-product of this we get a polynomial tim e recognition algorithm. It should be noted that our result does not c haracterize t-perfection, as that is not maintained when taking subgra phs but only when taking induced subgraphs.