{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T05:21:58Z","timestamp":1790745718216,"version":"4.1.0"},"reference-count":71,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"Jos\u00e9 Correa Amazon Research"},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012950","name":"Institut national de recherche en informatique et en automatique","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100012950","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>This paper deals with the characterization and the recognition of graph classes. A popular way to characterize a graph class is to list a minimal set of forbidden induced subgraphs. Unfortunately, this strategy rarely leads to a very efficient recognition algorithm. On the other hand, many graph classes can be efficiently recognized by techniques that use some ordering of the nodes, such as the one given by a traversal. We specifically study graphs that have an ordering avoiding some ordered structures. More precisely, we consider structures that we call patterns on three nodes, and we study the complexity of recognizing the classes associated with such patterns. In this domain, there are three key previous works. Independently Skrien [ J. Graph Theory, 6 (1982), pp. 309--316] and Damashke [Forbidden ordered subgraphs, in Topics in Combinatorics and Graph Theory, Physica-Verlag HD, 1990, pp. 219--229] noted that several graph classes, such as chordal, bipartite, interval, and comparability graphs, have a characterization in terms of forbidden patterns. On the algorithmic side, Hell, Mohar, and Rafiey [Ordering without forbidden patterns, in Algorithms--ESA 2014, Springer, 2014, pp. 554--565] proved that any class defined by a set of forbidden patterns on three nodes can be recognized in time $O(n^3)$ by using an algorithm based on an extension of 2-SAT. We improve on these two lines of works by systematically characterizing all the classes defined by sets of forbidden patterns (on three nodes) and proving that among the 22 different classes (up to complement) that we find, 20 can actually be recognized in linear time. Beyond these results, we consider that this type of characterization is very useful from an algorithmic perspective, leads to a rich structure of classes, and generates many algorithmic and structural open questions worth investigating.<\/jats:p>","DOI":"10.1137\/19m1280399","type":"journal-article","created":{"date-parts":[[2021,1,7]],"date-time":"2021-01-07T12:28:11Z","timestamp":1610022491000},"page":"55-90","source":"Crossref","is-referenced-by-count":10,"title":["Graph Classes and Forbidden Patterns on Three Vertices"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3994-0898","authenticated-orcid":true,"given":"Laurent","family":"Feuilloley","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michel","family":"Habib","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,1,7]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(79)90021-2"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9045-2"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"A. Brandst\u00e4dt, V. Le, and J. P. Spinrad,\n                      Graph Classes: A Survey\n                      , Discrete Math. Appl. 3, SIAM, 1999,https:\/\/doi.org\/10.1137\/1.9780898719796.","DOI":"10.1137\/1.9780898719796"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00470"},{"key":"atypb6","first-page":"154","volume":"2017","author":"Charbit P.","year":"2017","journal-title":"COCOA"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.12.009"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20165"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2006.164.51"},{"key":"atypb10","first-page":"63","volume":"21","author":"Chv\u00e1tal V.","year":"1984","journal-title":"Ann. Discrete Math."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70731-3"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2003.07.001"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/15M1012396"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/050623498"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193250125"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100373455"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21795"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-014-9661-y"},{"key":"atypb19","first-page":"219","author":"Damaschke P.","year":"1990","journal-title":"Physica-Verlag HD"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2005.03.003"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02992776"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070304"},{"key":"atypb24","first-page":"155","volume":"7","author":"Dujmovica V.","year":"2005","journal-title":"Discrete Math. Theoret. Comput. Sci."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.08.008"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.07.016"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.2307\/2371374"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1145\/321707.321710"},{"key":"atypb29","unstructured":"L. Feuilloley,\n                      Local Certification in Distributed Computing: Error-Sensitivity, Uniformity, Redundancy, and Interactivity\n                      , Ph.D. thesis, Universit\u00e9 Paris Diderot, 2018."},{"key":"atypb30","unstructured":"L. Feuilloley,\n                      Introduction to Local Certification\n                      , preprint,https:\/\/arxiv.org\/abs\/1910.12747, 2019."},{"key":"atypb31","first-page":"42","volume":"119","author":"Feuilloley L.","year":"2016","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"atypb32","unstructured":"L. Feuilloley and M. Habib,\n                      Graph Classes Defined by Forbidden Patterns: A Geometric Approach\n                      , manuscript, 2019."},{"key":"atypb33","first-page":"311","volume":"19","author":"Foldes S.","year":"1977","journal-title":"Congr. Numer."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1965.15.835"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60618-1_88"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020961"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1964-055-5"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90178-4"},{"key":"atypb39","unstructured":"M. Habib and R. Gaudy,\n                      On 2 Subquadratic Algorithms for Transitive Closure and Reduction\n                      , manuscript, 2018."},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2009.02.017"},{"key":"atypb41","unstructured":"M. Habib and L. Mouatadid,\n                      Maximum induced matching algorithms via vertex ordering characterizations\n                      , in 28th International Symposium on Algorithms and Computation, ISAAC 2017, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017, pp. 43:1-43:12,https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2017.43."},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579333"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.7.3.287"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1137\/0405031"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1137\/0221055"},{"key":"atypb46","first-page":"87","volume":"14","author":"Heggernes P.","year":"2007","journal-title":"Nord. J. Comput."},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_46"},{"key":"atypb48","first-page":"85","author":"Karp R. M.","year":"1972","journal-title":"NY"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1137\/0406032"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.4064\/fm-51-1-45-64"},{"key":"atypb51","first-page":"23","volume":"16","author":"Li P.","year":"2014","journal-title":"Discrete Math. Theoret. Comput. Sci."},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(93)90308-I"},{"key":"atypb53","unstructured":"N. V. Mahadev and U. N. Peled,\n                      Threshold Graphs and Related Topics\n                      , Ann. Discrete Math. 56, North-Holland, 1995."},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00319-7"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1971.11992886"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90075-9"},{"key":"atypb57","unstructured":"J. Nes\u0306etr\u0306il,\n                      private communication\n                      , 2017."},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90245-D"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90091-9"},{"key":"atypb60","unstructured":"F. Roberts,\n                      Indifference graphs\n                      , in Proof Techniques in Graph Theory, F. Harary, ed., Academic Press, 1969, pp. 301-310."},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1137\/0205021"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90063-X"},{"key":"atypb63","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199604)21:4<413::AID-JGT7>3.0.CO;2-S"},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190060307"},{"key":"atypb65","first-page":"169","volume":"17","author":"Soto M.","year":"2015","journal-title":"Discrete Math. Theoret. Comput. Sci."},{"key":"atypb66","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(87)80003-3"},{"key":"atypb67","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"},{"key":"atypb68","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"atypb69","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"},{"key":"atypb70","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1962-0172273-0"},{"key":"atypb71","unstructured":"D. R. Wood,\n                      Characterisations of Intersection Graphs by Vertex Orderings\n                      , preprint,https:\/\/arxiv.org\/abs\/cs\/0404031, 2004."},{"key":"atypb72","doi-asserted-by":"publisher","DOI":"10.1137\/0603036"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1280399","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:18:55Z","timestamp":1787321935000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1280399"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":71,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1280399"],"URL":"https:\/\/doi.org\/10.1137\/19m1280399","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}