2-nested matrices: towards understanding the structure of circle graphs. (English) Zbl 1492.05055
Summary: 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 characterized in terms of forbidden submatrices by A. Tucker [J. Comb. Theory, Ser. B 12, 153–162 (1972; Zbl 0208.52402)]. Several graph classes were characterized by means of this property, including interval graphs and strongly chordal digraphs. In this work, we define and characterize 2-nested matrices, which are \((0,1)\)-matrices with a variant of the C1P and for which there is also a 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 characterize split graphs that are also circle by minimal forbidden induced subgraphs.
MSC:
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C75 | Structural characterization of families of graphs |
Citations:
Zbl 0208.52402References:
| [1] | Annexstein, F. S., Swaminathan, R. P.: On testing consecutive-ones property in parallel. In Proceedings of the Seventh Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’95, pages 234-243, New York, NY, USA, 1995. Association for Computing Machinery · Zbl 0936.68111 |
| [2] | Basu, A.; Das, S.; Ghosh, S.; Sen, M., Circular-arc bigraphs and its subclasses, J. Graph Theory, 73, 4, 361-376 (2013) · Zbl 1269.05025 · doi:10.1002/jgt.21681 |
| [3] | Bonomo, F.; Durán, G.; Grippo, L.; Safe, M., Partial characterizations of circle graphs, Discrete Appl. Math., 159, 16, 1699-1706 (2011) · Zbl 1228.05243 · doi:10.1016/j.dam.2010.06.020 |
| [4] | Bonomo-Braberman, F., Durán, G., Pardal, N., Safe, M. D.: Forbidden induced subgraph characterization of circle graphs within split graphs. Discrete Appl. Math., In press., 2021. doi:10.1016/j.dam.2020.12.021 · Zbl 1502.05168 |
| [5] | Bouchet, A., Reducing prime graphs and recognizing circle graphs, Combinatorica, 7, 3, 243-254 (1987) · Zbl 0666.05037 · doi:10.1007/BF02579301 |
| [6] | Bouchet, A.: Circle graphs obstructions. J. Comb. Theory, Ser. B, 60(1):107-144, (1994) · Zbl 0793.05116 |
| [7] | Brijder, R., Traldi, L.: A characterization of circle graphs in terms of multimatroid representations. Electron. J. Comb., 27(1):P1.25, (2020) · Zbl 1431.05032 |
| [8] | Brijder, R.; Traldi, L., A characterization of circle graphs in terms of total unimodularity, Eur. J. Comb., 102 (2022) · Zbl 1486.05035 · doi:10.1016/j.ejc.2021.103455 |
| [9] | Cunningham, WH, Decomposition of directed graphs, SIAM J. Algebraic Discrete Methods, 3, 2, 214-228 (1982) · Zbl 0497.05031 · doi:10.1137/0603021 |
| [10] | Durán, G.; Grippo, L.; Safe, M., Structural results on circular-arc graphs and circle graphs: a survey and the main open problems, Discrete Appl. Math., 164, 427-443 (2014) · Zbl 1288.05054 · doi:10.1016/j.dam.2012.12.021 |
| [11] | Even, S., Itai, A.: Queues, stacks, and graphs. In Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971), pages 71-86, (1971) |
| [12] | Even, S.; Pnueli, A.; Lempel, A., Permutation graphs and transitive graphs, J. Assoc. Comput. Mach., 19, 400-410 (1972) · Zbl 0251.05113 · doi:10.1145/321707.321710 |
| [13] | Feder, T.; Hell, P.; Huang, J.; Rafiey, A., Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms, Discrete Appl. Math., 160, 6, 697-707 (2012) · Zbl 1236.05092 · doi:10.1016/j.dam.2011.04.016 |
| [14] | Fishburn, P. C.: Interval orders and interval graphs. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Ltd., Chichester, 1985. A study of partially ordered sets, A Wiley-Interscience Publication · Zbl 0568.05047 |
| [15] | Földes, S., Hammer, P. L.: Split graphs. Technical Report Technical Report CORR 76-3, University of Waterloo, Waterloo, Canada, (1976) · Zbl 0407.05071 |
| [16] | Fulkerson, DR; Gross, OA, Incidence matrices and interval graphs, Pacific J. Math., 15, 835-855 (1965) · Zbl 0132.21001 · doi:10.2140/pjm.1965.15.835 |
| [17] | Gallai, T., Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar., 18, 25-66 (1967) · Zbl 0153.26002 · doi:10.1007/BF02020961 |
| [18] | Garey, MR; Johnson, DS; Miller, GL; Papadimitriou, CH, The complexity of coloring circular arcs and chords, SIAM J. Alg. Disc. Meth., 1, 2, 216-227 (1980) · Zbl 0499.05058 · doi:10.1137/0601025 |
| [19] | Gavril, F., Algorithms on circular-arc graphs, Networks, 4, 357-369 (1974) · Zbl 0309.05126 · doi:10.1002/net.3230040407 |
| [20] | Geelen, J.; Oum, S., Circle graph obstructions under pivoting, J. Graph Theory, 61, 1, 1-11 (2009) · Zbl 1207.05189 · doi:10.1002/jgt.20363 |
| [21] | Gioan, E.; Paul, C.; Tedder, M.; Corneil, D., Practical and efficient circle graph recognition, Algorithmica, 69, 4, 759-788 (2014) · Zbl 1303.05190 · doi:10.1007/s00453-013-9745-8 |
| [22] | Golumbic, M.C.: Algorithmic graph theory and perfect graphs, volume 57 of Annals of Discrete Mathematics. Elsevier Science B.V., Amsterdam, second edition, 2004. With a foreword by Claude Berge · Zbl 1050.05002 |
| [23] | Hsu, W.-L.: On physical mapping algorithms: an error-tolerant test for the consecutive ones property. In Computing and combinatorics (Shanghai, 1997), volume 1276 of Lecture Notes in Comput. Sci., pages 242-250. Springer, Berlin, (1997) |
| [24] | Lin, MC; Soulignac, FJ; Szwarcfiter, JL, Normal Helly circular-arc graphs and its subclasses, Discrete Appl. Math., 161, 7-8, 1037-1059 (2013) · Zbl 1263.05064 · doi:10.1016/j.dam.2012.11.005 |
| [25] | Lipski, W., Generalizations of the consecutive ones property and related np-complete problems, Fund. Inform., 6, 1, 53-69 (1983) · Zbl 0534.68030 |
| [26] | McConnell, R., Linear-time recognition of circular-arc graphs, Algorithmica, 37, 2, 93-147 (2003) · Zbl 1060.68088 · doi:10.1007/s00453-003-1032-7 |
| [27] | Mertzios, GB, A matrix characterization of interval and proper interval graphs, Appl. Math. Lett., 21, 4, 332-337 (2008) · Zbl 1139.05041 · doi:10.1016/j.aml.2007.04.001 |
| [28] | Naji, W., Reconnaissance des graphes de cordes, Discret. Math., 54, 329-337 (1985) · Zbl 0567.05033 · doi:10.1016/0012-365X(85)90117-7 |
| [29] | Pardal, N.: Structural characterization of some problems on circle and interval graphs. PhD thesis, Universidad de Buenos Aires - Université Sorbonne Paris-Nord, 2020. arXiv:2006.00099 |
| [30] | Pardal, N.; Durán, GA; Grippo, LN; Safe, MD, On nested and 2-nested graphs: two subclasses of graphs between threshold and split graphs, Mat. Contemp., 46, 119-128 (2018) · Zbl 07837951 |
| [31] | Roberts, FS, On the compatibility between a graph and a simple order, J. Combinatorial Theory Ser. B, 11, 28-38 (1971) · Zbl 0177.27003 · doi:10.1016/0095-8956(71)90010-4 |
| [32] | Safe, MD, Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property, J. Graph Theory, 93, 2, 268-298 (2020) · Zbl 1495.05067 · doi:10.1002/jgt.22486 |
| [33] | Safe, MD, Circularly compatible ones, \(D\)-circularity, and proper circular-arc bigraphs, SIAM J. Discrete Math., 35, 2, 707-751 (2021) · Zbl 1462.05311 · doi:10.1137/19M1266162 |
| [34] | Sen, M.; Das, S.; Roy, AB; West, DB, Interval digraphs: an analogue of interval graphs, J. Graph Theory, 13, 2, 189-202 (1989) · Zbl 0671.05039 · doi:10.1002/jgt.3190130206 |
| [35] | Sen, M.; Das, S.; West, DB, Circular-arc digraphs: a characterization, J. Graph Theory, 13, 5, 581-592 (1989) · Zbl 0689.05025 · doi:10.1002/jgt.3190130508 |
| [36] | Sen, M.; Sanyal, BK, Indifference digraphs: a generalization of indifference graphs and semiorders, SIAM J. Discrete Math., 7, 2, 157-165 (1994) · Zbl 0798.05025 · doi:10.1137/S0895480190177145 |
| [37] | Traldi, L., Splitting cubic circle graphs, Discuss. Math. Graph Theory, 36, 3, 723-741 (2016) · Zbl 1339.05327 · doi:10.7151/dmgt.1894 |
| [38] | Tucker, A., Matrix characterizations of circular-arc graphs, Pacific J. Math., 39, 535-545 (1971) · Zbl 0226.05125 · doi:10.2140/pjm.1971.39.535 |
| [39] | Tucker, A., A structure theorem for the consecutive \(1\)’s property, J. Combinatorial Theory Ser. B, 12, 153-162 (1972) · Zbl 0208.52402 · doi:10.1016/0095-8956(72)90019-6 |
| [40] | Tucker, A.C.: Two characterizations of proper circular-arc graphs. PhD thesis, Stanford University, (1969) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
