On finite characterizability of graphs with restricted equivalence partition number in classes of polar graphs

T. V. Lubasheva, Yu. M. Metelsky

Belarusian State University

Abstract: Let $L^l(k)$ be the class of graphs with equivalence partition number at most $k$. In this paper the class of polar graphs is represented as the union of classes in each of them the problem of existence of finite characterization in terms of forbidden induced subgraphs for the class $L^l(k)$ is solved. Thus, in particular, for any fixed integers $k\ge3$ and $\alpha,\beta\in\mathbb N\cup\{\infty\}$, a complete description of finite characterizability for the class $L^l(k)$ in the classes of $(\alpha,\beta)$-polar graphs is obtained.

UDC: 519.1

Received: 23.09.2010