A forbidden subgraph characterization of nested and 2-nested graphs

NINA PARDAL; GUILLERMO A. DURÁN; MARTÍN D. SAFE

Río de Janeiro

Workshop; Latin-American Workshop on Clique in Graphs 2018; 2018

UFRJ-UERJ-CEFET/RJ

We say a (0, 1)-matrix is nested if it has the consecutive ones property for the rows (C1P) and every two rows are disjoint or nested (i.e., one is included in the other). We say a (0, 1)-matrix is 2-nested if it has the C1P and admits a partition of its rows into two sets such that the submatrix induced by each of these sets is nested. We say a split graph G with split partition (K, S) is nested (resp. 2-nested) if the matrix A(S, K) -which indicates the adjacency between vertices in S and K- is nested (resp. 2-nested). In this work, we characterize nested and 2-nested matrices by minimal forbidden submatrices. This implies a minimal forbidden induced subgraph characterization for nested and 2-nested graphs. Our result relies on a characterization of the consecutive ones property by minimal forbidden submatrices (Tucker, 1972).Circle graphs (Even and Itai, 1971) are intersection graphs of chords in a circle. These graphs were characterized by Bouchet in 1994 by forbidden induced subgraphs of locally equivalent graphs. However, no complete characterizations of circle graphs by forbidden induced subgraphs of the graph itself is known. Nested and 2-nested graphs are common subclasses of the classes of threshold graphs and circle graphs. 2-nested graph characterization arises as a natural subproblem in our ongoing efforts to characterize those split graphs that are circle graphs by minimal forbidden induced subgraphs.