{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:34:36Z","timestamp":1787322876395,"version":"build-2736575974"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>We propose bipartite analogues of comparability and cocomparability graphs. Surprisingly, the two classes coincide. We call these bipartite graphs cocomparability bigraphs. We characterize cocomparability bigraphs in terms of vertex orderings, forbidden substructures, and orientations of their complements. In particular, we prove that cocomparability bigraphs are precisely those bipartite graphs that do not have edge-asteroids; this is analogous to Gallai's structural characterization of cocomparability graphs by the absence of (vertex-) asteroids. Our characterizations imply a robust polynomial-time recognition algorithm for the class of cocomparability bigraphs. Finally, we also discuss a natural relation of cocomparability bigraphs to interval containment bigraphs, resembling a well-known relation of cocomparability graphs to interval graphs.<\/jats:p>","DOI":"10.1137\/19m1263789","type":"journal-article","created":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T10:50:16Z","timestamp":1600167016000},"page":"1969-1983","source":"Crossref","is-referenced-by-count":4,"title":["Bipartite Analogues of Comparability and Cocomparability Graphs"],"prefix":"10.1137","volume":"34","author":[{"given":"Pavol","family":"Hell","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0786-2271","authenticated-orcid":true,"given":"Jing","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jephian C.-H.","family":"Lin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ross M.","family":"McConnell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,9,15]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90028-2"},{"key":"atypb2","unstructured":"A. Brandst\u00e4dt, V. B. Le, and J. Spinrad,\n                      Graph Classes\n                      , SIAM Monographs on Discrete Math. and Appl., SIAM, Philadelphia, 1999."},{"key":"atypb3","first-page":"79","volume":"157","author":"Brown D. E.","year":"2002","journal-title":"Congr. Numer."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)90221-9"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193250125"},{"key":"atypb6","first-page":"219","author":"Damaschke P.","year":"1990","journal-title":"Heidelberg"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02276883"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s004939970003"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020961"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1964-055-5"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic,\n                      Algorithmic Graph Theory and Perfect Graphs\n                      , Academic Press, New York, 1980.","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190020209"},{"key":"atypb13","first-page":"739","volume":"23","author":"Harary F.","year":"1982","journal-title":"Comment. Math. Univ. Carolin."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20006"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/0606070"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.01.001"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.02.001"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/0606070"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00054-H"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.11.020"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.4064\/fm-51-1-45-64"},{"key":"atypb22","unstructured":"A. Lubiw,\n                      $\\Gamma$-Free Matrices\n                      , Master's thesis, University of Waterloo, Waterloo, ON, Canada, 1982."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/0216057"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1032-7"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00319-7"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00027-9"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/0216062"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.05.020"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130206"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00167-H"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.06.002"},{"key":"atypb32","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\/19M1263789","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:31:01Z","timestamp":1787319061000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1263789"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/19M1263789"],"URL":"https:\/\/doi.org\/10.1137\/19m1263789","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}