2
$\begingroup$

Let $G$ be a graph without any hole or antihole of odd length at least 5 (i.e. $G$ is a Berge graph and so by the Strong Perfect Graph Theorem, $G$ is perfect). Assume further that $G$ has no antihole of length 6 and also it has no even hole or antihole of length at least 8. Also suppose that $G$ has no induced path $P_6$ of length 6.

Thus graphs in question are perfect and $P_6$-free with a slightly stronger property that they have no antihole of length 6.

Is there a classification of such graphs?

Of course one may expect that by docomposion results due to [M. Chudnovsky, N. Robertson, P.D. Seymour, R.Thomas, V. Chvátal, N. Sbihi, M. Conforti, G. Cornuéjols, and K. Vušković] for perfect graphs and also by the results due to [R. Mosca, Pim van 't Hof and DaniÄel Paulusma] on P6-free graph, it may be possible to find a characterization or even a classification; but, for a lazy man as me, it is better to know first if such a characterization has been aleardy seen or used.

The motivation is this question of mine about graphs $G$ which are cospectral with a friendship graph. Such a graph $G$ has no induced subgraph with two eigenvalues greater than 1 and also no induced subgraph of $G$ has two eigenvalues less than -1. The latter follows from the interlacing lemma.
Thus it is easily seen that such graphs $G$ are perfect and $P_6$-free and they have no antihole of length 6.

$\endgroup$
2

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.