{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:15Z","timestamp":1787323515166,"version":"build-2736575974"},"reference-count":38,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["KO 1053\/8-1"],"award-info":[{"award-number":["KO 1053\/8-1"]}],"id":[{"id":"10.13039\/501100001659","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>As is well known, the isomorphism problem for vertex-colored graphs with color multiplicity at most 3 is solvable by the classical two-dimensional Weisfeiler--Leman algorithm (2-WL). On the other hand, the prominent Cai--F\u00fcrer--Immerman construction shows that even the multidimensional version of the algorithm does not suffice for graphs with color multiplicity 4. We give an efficient decision procedure that, given a graph $G$ of color multiplicity 4, recognizes whether or not $G$ is identifiable by 2-WL, that is, whether or not 2-WL distinguishes $G$ from every nonisomorphic graph. In fact, we solve the much more general problem of recognizing whether or not a given coherent configuration of maximum fiber size 4 is separable. This extends our recognition algorithm to graphs of color multiplicity 4 with directed and colored edges. Our decision procedure is based on an explicit description of the class of graphs with color multiplicity 4 that are not identifiable by 2-WL. The Cai--F\u00fcrer--Immerman graphs of color multiplicity 4 distinctly appear here as a natural subclass, which demonstrates that the Cai--F\u00fcrer--Immerman construction is not ad hoc. Our classification reveals also other types of graphs that are hard for 2-WL. One of them arises from patterns known as $(n_3)$-configurations in incidence geometry.<\/jats:p>","DOI":"10.1137\/20m1327550","type":"journal-article","created":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T14:43:59Z","timestamp":1629384239000},"page":"1792-1853","source":"Crossref","is-referenced-by-count":6,"title":["Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6007-0922","authenticated-orcid":true,"given":"Frank","family":"Fuhlbr\u00fcck","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johannes","family":"K\u00f6bler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oleg","family":"Verbitsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,8,19]]},"reference":[{"key":"atypb1","first-page":"384","author":"Arvind V.","year":"2006","journal-title":"New York"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0147-6"},{"key":"atypb3","first-page":"13","author":"Arvind V.","year":"2005","journal-title":"IEEE Computer Society"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"L. Babai,\n                      Graph isomorphism in quasipolynomial time\n                      , in Proceedings of the 48th Annual ACM Symposium on Theory of Computing, 2016, pp. 684-697,https:\/\/doi.org\/doi.acm.org\/10.1145\/2897518.2897542.","DOI":"10.1145\/2897518.2897542"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73545-X"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706356"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1974-0331751-8"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01374526"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"atypb10","unstructured":"G. Chen and I. Ponomarenko,\n                      Coherent Configurations\n                      , Central China Normal University Press, Wuhan, 2019."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/2528404"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00492"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"B. de Bruyn,\n                      An Introduction to Incidence Geometry\n                      , Front. Math., Birkh\u00e4user\/Springer, Basel, 2016.","DOI":"10.1007\/978-3-319-43811-5"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.37236\/1450"},{"key":"atypb15","first-page":"189","volume":"14","author":"Evdokimov S.","year":"2003","journal-title":"St. Petersburg Math. J."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00152-7"},{"key":"atypb17","unstructured":"F. Fuhlbr\u00fcck, J. K\u00f6bler, and O. Verbitsky,\n                      Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm\n                      , in 37th Annual Symposium on Theoretical Aspects of Computer Science (STACS'20), LIPIcs Leibniz Int. Proc. Inform. 154, Schloss Dagstuhl Leibniz-Zentrum f\u00fcr Informatik, 2020, 43,https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.43."},{"key":"atypb18","first-page":"260","author":"F\u00fcrer M.","year":"2017","journal-title":"New York"},{"key":"atypb19","first-page":"296","author":"Gall F. L.","year":"2014","journal-title":"ACM"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"B. Gr\u00fcnbaum,\n                      Configurations of Points and Lines\n                      , Grad. Stud. Math. 103, AMS, Providence, RI, 2009.","DOI":"10.1090\/gsm\/103"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.2307\/2275675"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01111335"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2018.05.027"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90007-4"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"N. Immerman,\n                      Descriptive Complexity\n                      , Grad. Texts Comput. Sci., Springer, New York, 1999,https:\/\/doi.org\/10.1007\/978-1-4612-0539-5.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"atypb26","first-page":"59","author":"Immerman N.","year":"1990","journal-title":"New York"},{"key":"atypb27","first-page":"319","author":"Kiefer S.","year":"2015","journal-title":"New York"},{"key":"atypb28","unstructured":"M. Klin, M. Muzychuk, and S. Reichard,\n                      Wallis-Fon-Der-Flaass Coherent Configurations on 16 Points and Related Combinatorial Structures\n                      , manuscript, 2006."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-016-0258-8"},{"key":"atypb30","first-page":"292","author":"Luks E. M.","year":"1986","journal-title":"IEEE"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"K. Metsch,\n                      Linear Spaces with Few Lines\n                      , Lect. Notes Math. 1490, Springer-Verlag, Berlin, 1991.","DOI":"10.1007\/BFb0083245"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2011.11.012"},{"key":"atypb33","first-page":"60","author":"Neuen D.","year":"2017","journal-title":"ESA."},{"key":"atypb34","first-page":"138","author":"Neuen D.","year":"2018","journal-title":"ACM"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"T. Pisanski and B. Servatius,\n                      Configurations from a Graphical Viewpoint\n                      , Birkh\u00e4user Adv. Texts Basler Lehrb\u00fccher, Birkh\u00e4user, New York, 2013.","DOI":"10.1007\/978-0-8176-8364-1"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"atypb37","first-page":"9","volume":"2","author":"Weisfeiler B.","year":"1968","journal-title":"Nauchno-Technicheskaya Informatsia Ser."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90252-O"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1327550","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:06:57Z","timestamp":1787321217000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1327550"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1327550"],"URL":"https:\/\/doi.org\/10.1137\/20m1327550","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}