2016/11/07 by Martín D. Safe, Safe, Martín D. · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Digital Image Processing Techniques
paper · pdf · doi:10.48550/arxiv.1611.02216
A graph is concave-round if its vertices can be circularly enumerated so that\nthe closed neighbourhood of each vertex is an interval in the enumeration. In\nthis work, we give a minimal forbidden induced subgraph characterization for\nthe class of concave-round graphs, solving a problem posed by Bang-Jensen,\nHuang, and Yeo [SIAM J Discrete Math, 13:179--193, 2000]. In addition, we show\nthat it is possible to find one such forbidden induced subgraph in linear time\nin any given graph that is not concave-round. As part of the analysis, we\nobtain characterizations by minimal forbidden submatrices for the circular-ones\nproperty for rows and for the circular-ones property for rows and columns and\nshow that, also for both variants of the property, one of the corresponding\nforbidden submatrices can be found (if present) in any given matrix in linear\ntime. We make some final remarks regarding connections to some classes of\ncircular-arc graphs.\n