2-nested matrices: towards understanding the structure of circle graphs

DOI10.1007/S00373-022-02510-1MaRDI QIDQ2152610zbMATH OpenOpenAlexWikidataFDO

Authors Guillermo Durán, Nina Pardal, Martín D. Safe

Publication date 8 July 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.03795

zbMATH Keywords

split graphscircle graphsconsecutive-ones property2-nested matrices

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Structural characterization of families of graphs (05C75)

Abstract: A $(0,1)$-matrix has the consecutive-ones property (C1P) if its columns can be permuted to make the $1$'s in each row appear consecutively. This property was characterised in terms of forbidden submatrices by Tucker in 1972. Several graph classes were characterised by means of this property, including interval graphs and strongly chordal digraphs. In this work, we define and characterise 2-nested matrices, which are $(0,1)$-matrices with a variant of the C1P and for which there is also certain assignment of one of two colors to each block of consecutive $1$'s in each row. The characterization of 2-nested matrices in the present work is of key importance to characterise split graphs that are also circle by minimal forbidden induced subgraphs.

Recommendations

• Forbidden induced subgraph characterization of circle graphs within split graphs
• On finding Tucker submatrices and Lekkerkerker-Boland subgraphs
• On nested split graphs whose second largest eigenvalue is less than 1
• A tight bound on the length of odd cycles in the incompatibility graph of a non-C1P matrix
• Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs

Cites work

• scientific article; zbMATH DE number 3848609 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• A characterization of circle graphs in terms of multimatroid representations
• A characterization of circle graphs in terms of total unimodularity
• A matrix characterization of interval and proper interval graphs
• A structure theorem for the consecutive 1's property
• Algorithmic graph theory and perfect graphs
• Algorithms on circular-arc graphs
• Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property
• Circle graph obstructions
• Circle graph obstructions under pivoting
• Circular-arc bigraphs and its subclasses
• Circularly compatible ones, \(D\)-circularity, and proper circular-arc bigraphs
• Circular‐arc digraphs: A characterization
• Decomposition of Directed Graphs
• Forbidden induced subgraph characterization of circle graphs within split graphs
• Incidence matrices and interval graphs
• Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
• Interval digraphs: An analogue of interval graphs
• Interval graphs and interval orders
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Linear-time recognition of circular-arc graphs
• Matrix characterizations of circular-arc graphs
• Normal Helly circular-arc graphs and its subclasses
• On testing consecutive-ones property in parallel
• On the compatibility between a graph and a simple order
• Partial characterizations of circle graphs
• Permutation Graphs and Transitive Graphs
• Practical and efficient circle graph recognition
• Reconnaissance des graphes de cordes
• Reducing prime graphs and recognizing circle graphs
• Splitting cubic circle graphs
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• The Complexity of Coloring Circular Arcs and Chords
• Transitiv orientierbare Graphen

Cited in

(1)

• On nested and 2-nested graphs: two subclasses of graphs between threshold and split graphs

This page was built for publication: 2-nested matrices: towards understanding the structure of circle graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2152610)