{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,14]],"date-time":"2026-09-14T17:33:25Z","timestamp":1789407205410,"version":"build-2803163510"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We introduce the class of strong cocomparability graphs, as the class of reflexive graphs whose adjacency matrix can be rearranged by a simultaneous row and column permutation to avoid the submatrix with rows 01,10, which we call Slash. We provide an ordering characterization, a forbidden structure characterization, and a polynomial-time certifying recognition algorithm for the class. These results complete the picture in which in addition to, or instead of, the [Formula: see text] matrix one forbids the [Formula: see text] matrix (which has rows 11,10). It is well known that in these two cases one obtains the class of interval graphs and the class of strongly chordal graphs, respectively. By complementation, we obtain the class of strong comparability graphs, whose adjacency matrix can be rearranged by a simultaneous row and column permutation to avoid the two-by-two identity submatrix. Thus our results give characterizations and algorithms for this class of irreflexive graphs as well. In other words, our results may be interpreted as solving the following problem: given a symmetric 0,1-matrix with 0-diagonal, can the rows and columns of be simultaneously permuted to avoid the two-by-two identity submatrix?<\/jats:p>","DOI":"10.1137\/22m153238x","type":"journal-article","created":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T04:28:07Z","timestamp":1707712087000},"page":"828-844","source":"Crossref","is-referenced-by-count":2,"title":["Strong Cocomparability Graphs and Slash-Free Orderings of Matrices"],"prefix":"10.1137","volume":"38","author":[{"given":"Pavol","family":"Hell","sequence":"first","affiliation":[{"name":"School of Computing Science, Simon Fraser University, Burnaby V5A 1S6, BC, Canada."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0786-2271","authenticated-orcid":true,"given":"Jing","family":"Huang","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, University of Victoria, Victoria V8W 2Y2, BC, Canada."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0119-9376","authenticated-orcid":true,"given":"Jephian C.-H.","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung 80424, Taiwan."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,2,12]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90028-2"},{"key":"ref2","unstructured":"V. L. Beresnev  and \nA. I. Davydov  , On matrices with the connectedness property, Upravlyaemye Sistemy, 19 (1979), pp. 3\u201313 (in Russian)."},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"J. Bok , \nR. Brewster , \nP. Hell , \nN. Jedli\u010dkov\u00e1 , and \nA. Rafiey  , Min Orderings and List Homomorphism Dichotomies for Signed and Unsigned Graphs, arXiv:2206.01068 [math.CO], 2022.","DOI":"10.1007\/978-3-031-20624-5_31"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"P. Damaschke  , Forbidden ordered subgraphs, Top. Combin. Graph Theory, (1990), pp. 219\u2013229.","DOI":"10.1007\/978-3-642-46908-4_25"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90154-1"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90061-1"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s004939970003"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.04.016"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"M. Francis , \nP. Hell , and \nJ. Stacho  , Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm, in Proceedings of SODA, 2015.","DOI":"10.1137\/1.9781611973730.114"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"T. Gallai  , Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hungar., 18 (1967), pp. 25\u201366.","DOI":"10.1007\/BF02020961"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1964-055-5"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190020209"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/20M1316056"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/19M1263789"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/19M1241763"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_51"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_46"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/100783844"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/0606070"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.01.001"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.02.001"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90025-2"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00054-H"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/0406032"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.4064\/fm-51-1-45-64"},{"key":"ref27","unstructured":"A. Lubiw  , \\(\\Gamma\\)-free Matrices, Master\u2019s thesis, University of Waterloo, 1982."},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/0216057"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1137\/0216062"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"A. M. Shresta , \nS. Tayu , and \nS. Ueno  , On two-directional orthogonal ray graphs, in Proceedings of the 2010 IEEE International Symposium on Circuits and Systems, IEEE, 2010, pp. 1807\u20131810.","DOI":"10.1109\/ISCAS.2010.5537709"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1090\/fim\/019"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(87)80003-3"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M153238X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:57:25Z","timestamp":1787317045000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M153238X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,12]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1137\/22M153238X"],"URL":"https:\/\/doi.org\/10.1137\/22m153238x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,12]]}}}