{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T16:58:58Z","timestamp":1782233938303,"version":"3.54.5"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,12,19]],"date-time":"2016-12-19T00:00:00Z","timestamp":1482105600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2017,9]]},"DOI":"10.1007\/s00037-016-0147-6","type":"journal-article","created":{"date-parts":[[2016,12,19]],"date-time":"2016-12-19T09:20:56Z","timestamp":1482139256000},"page":"627-685","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Graph Isomorphism, Color Refinement, and Compactness"],"prefix":"10.1007","volume":"26","author":[{"given":"V.","family":"Arvind","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johannes","family":"K\u00f6bler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gaurav","family":"Rattan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oleg","family":"Verbitsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,12,19]]},"reference":[{"key":"147_CR1","unstructured":"Dana Angluin (1980). Local and global properties in networks of processors. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 82\u201393. ACM."},{"key":"147_CR2","doi-asserted-by":"crossref","unstructured":"V. Arvind, Johannes K\u00f6bler, Gaurav Rattan & Oleg Verbitsky (2015a). On the power of color refinement. In Proceedings of the 20th International Symposium on Fundamentals of Computation Theory (FCT), volume 9210 of Lecture Notes in Computer Science, 339\u2013350. Springer.","DOI":"10.1007\/978-3-319-22177-9_26"},{"key":"147_CR3","doi-asserted-by":"crossref","unstructured":"V. Arvind, Johannes K\u00f6bler, Gaurav Rattan & Oleg Verbitsky (2015b). On Tinhofer\u2019s linear programming approach to isomorphism testing. In Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 9235 of Lecture Notes in Computer Science, 26\u201337. Springer.","DOI":"10.1007\/978-3-662-48054-0_3"},{"issue":"1","key":"147_CR4","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1137\/120867834","volume":"42","author":"Albert Atserias","year":"2013","unstructured":"Atserias Albert, Maneva Elitza N. (2013) Sherali-Adams relaxations and indistinguishability in counting logics. SIAM Journal on Computing 42(1): 112\u2013137","journal-title":"SIAM Journal on Computing"},{"key":"147_CR5","unstructured":"L\u00e1szl\u00f3 Babai (1995). Automorphism groups, isomorphism, reconstruction. In Handbook of Combinatorics, chapter 27, 1447\u20131540. Elsevier."},{"issue":"3","key":"147_CR6","doi-asserted-by":"crossref","first-page":"628","DOI":"10.1137\/0209047","volume":"9","author":"Babai L\u00e1szl\u00f3","year":"1980","unstructured":"L\u00e1szl\u00f3 Babai, Paul Erd\u0151s & Stanley M. Selkow (1980) Random graph isomorphism. SIAM Journal on Computing 9(3): 628\u2013635","journal-title":"SIAM Journal on Computing"},{"key":"147_CR7","unstructured":"L\u00e1szl\u00f3 Babai & Ludek Ku\u010dera (1979). Canonical labelling of graphs in linear average time. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 39\u201346."},{"key":"147_CR8","doi-asserted-by":"crossref","unstructured":"Christoph Berkholz, Paul Bonsma & Martin Grohe (2013). Tight lower and upper bounds for the complexity of canonical colour refinement. In Proceedings of 21st Annual European Symposium on Algorithms (ESA), volume 8125 of Lecture Notes in Computer Science, 145\u2013156. Springer.","DOI":"10.1007\/978-3-642-40450-4_13"},{"key":"147_CR9","doi-asserted-by":"crossref","unstructured":"Alessandro Borri, Tiziana Calamoneri & Rossella Petreschi (2011). Recognition of unigraphs through superposition of graphs. Journal of Graph Algorithms and Applications 15(3), 323\u2013343.","DOI":"10.7155\/jgaa.00229"},{"key":"147_CR10","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0024-3795(88)90239-X","volume":"107","author":"Brualdi Richard A.","year":"1988","unstructured":"Richard A. Brualdi (1988) Some applications of doubly stochastic matrices. Linear Algebra and its Applications 107: 77\u2013100","journal-title":"Linear Algebra and its Applications"},{"key":"147_CR11","doi-asserted-by":"crossref","unstructured":"Richard A. Brualdi (2006). Combinatorial matrix classes. Cambridge University Press.","DOI":"10.1017\/CBO9780511721182"},{"key":"147_CR12","unstructured":"Robert G. Busacker & Thomas L. Saaty (1965). Finite graphs and networks: an introduction with applications. International Series in Pure and Applied Mathematics. McGraw-Hill Book Company, New York etc."},{"key":"147_CR13","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Martin F\u00fcrer & Neil Immerman (1992). An optimal lower bound on the number of variables for graph identification. Combinatorica 12(4), 389\u2013410.","DOI":"10.1007\/BF01305232"},{"key":"147_CR14","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(82)90016-0","volume":"19","author":"A. Cardon","year":"1982","unstructured":"Cardon A., Maxime Crochemore (1982) Partitioning a graph in $${O(|A| \\log_2 |V|)}$$ O ( | A | log 2 | V | ) . Theoretical Computer Science 19: 85\u201398","journal-title":"Theoretical Computer Science"},{"key":"147_CR15","doi-asserted-by":"crossref","unstructured":"Ada Chan & Chris D. Godsil (1997). Symmetry and eigenvectors. In Graph symmetry, volume 497, 75\u2013106. Kluwer Acad. Publ., Dordrecht.","DOI":"10.1007\/978-94-015-8937-6_3"},{"key":"147_CR16","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/S0012-365X(99)90071-7","volume":"197-198","author":"Evdokimov Sergei","year":"1999","unstructured":"Sergei Evdokimov, Marek Karpinski, Ilia N. Ponomarenko (1999) Compact cellular algebras and permutation groups. Discrete Mathematics 197-198: 247\u2013267","journal-title":"Discrete Mathematics"},{"key":"147_CR17","doi-asserted-by":"crossref","unstructured":"Sergei Evdokimov, Ilia N. Ponomarenko & Gottfried Tinhofer (2000). Forestal algebras and algebraic forests (on a new class of weakly compact graphs). Discrete Mathematics 225(1\u20133), 149\u2013172.","DOI":"10.1016\/S0012-365X(00)00152-7"},{"issue":"1\u20133","key":"147_CR18","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/S0024-3795(97)83595-1","volume":"255","author":"D. Godsil Chris","year":"1997","unstructured":"Godsil Chris D. (1997) Compact graphs and equitable partitions. Linear Algebra and its Applications 255(1\u20133): 259\u2013266","journal-title":"Linear Algebra and its Applications"},{"key":"147_CR19","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1008354.1008356","volume":"9","author":"M. Goldschlager Leslie","year":"1977","unstructured":"Goldschlager Leslie M. (1977) The monotone and planar circuit value problems are log space complete for P. SIGACT News 9: 25\u201329","journal-title":"SIGACT News"},{"issue":"4","key":"147_CR20","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1007\/s004939970004","volume":"19","author":"Grohe Martin","year":"1999","unstructured":"Martin Grohe (1999) Equivalence in finite-variable logics is complete for polynomial time. Combinatorica 19(4): 507\u2013532","journal-title":"Combinatorica"},{"key":"147_CR21","doi-asserted-by":"crossref","unstructured":"Martin Grohe, Kristian Kersting, Martin Mladenov & Erkal Selman (2014). Dimension reduction via colour refinement. In Proceeding of 22th Annual European Symposium on Algorithms (ESA), volume 8737 of Lecture Notes in Computer Science, 505\u2013516. Springer.","DOI":"10.1007\/978-3-662-44777-2_42"},{"issue":"3","key":"147_CR22","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1017\/jsl.2015.28","volume":"80","author":"Grohe Martin","year":"2015","unstructured":"Martin Grohe, Martin Otto (2015) Pebble games and linear equations. The Journal of Symbolic Logic 80(3): 797\u2013844","journal-title":"The Journal of Symbolic Logic"},{"key":"147_CR23","doi-asserted-by":"crossref","unstructured":"Neil Immerman & Eric Lander (1990). Describing graphs: A first-order approach to graph canonization. In Complexity Theory Retrospective, 59\u201381. Springer.","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"147_CR24","doi-asserted-by":"crossref","first-page":"143","DOI":"10.2140\/pjm.1975.56.143","volume":"56","author":"H. Johnson Robert","year":"1975","unstructured":"Johnson Robert H. (1975) Simple separable graphs. Pacific Journal of Mathematics 56: 143\u2013158","journal-title":"Pacific Journal of Mathematics"},{"key":"147_CR25","doi-asserted-by":"crossref","unstructured":"Kristian Kersting, Martin Mladenov, Roman Garnett & Martin Grohe (2014). Power iterated color refinement. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 1904\u20131910. AAAI Press.","DOI":"10.1609\/aaai.v28i1.8992"},{"key":"147_CR26","doi-asserted-by":"crossref","unstructured":"Sandra Kiefer, Pascal Schweitzer & Erkal Selman (2015). Graphs identified by logics with counting. In Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 9234 of Lecture Notes in Computer Science, 319\u2013330. Springer. A full version is available as an e-print http:\/\/arxiv.org\/abs\/1503.08792 .","DOI":"10.1007\/978-3-662-48057-1_25"},{"key":"147_CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0333-9","volume-title":"The graph isomorphism problem: its structural complexity","author":"K\u00f6bler Johannes","year":"1993","unstructured":"Johannes K\u00f6bler, Uwe Sch\u00f6ning, Jacobo Tor\u00e1n (1993) The graph isomorphism problem: its structural complexity. MA: Birkh\u00e4user., Boston"},{"issue":"3","key":"147_CR28","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/S0095-8956(76)80006-8","volume":"21","author":"Koren Michael","year":"1976","unstructured":"Michael Koren (1976) Pairs of sequences with a unique realization by bipartite graphs. Journal of Combinatorial Theory, Series B 21(3): 224\u2013234","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"147_CR29","unstructured":"Andreas Krebs & Oleg Verbitsky (2015). Universal covers, color refinement, and two-variable logic with counting quantifiers: Lower bounds for the depth. In Proceedings of the 30-th ACM\/IEEE Annual Symposium on Logic in Computer Science (LICS), 689\u2013700. IEEE Computer Society."},{"issue":"3","key":"147_CR30","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0095-8956(82)90042-9","volume":"33","author":"Leighton Frank Thomson","year":"1982","unstructured":"Frank Thomson Leighton (1982) Finite common coverings of graphs. Journal of Combinatorial Theory, Series B 33(3): 231\u2013238","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"147_CR31","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.disopt.2014.01.004","volume":"12","author":"N. Malkin Peter","year":"2014","unstructured":"Malkin Peter N. (2014) Sherali-Adams relaxations of graph isomorphism polytopes. Discrete Optimization 12: 73\u201397","journal-title":"Discrete Optimization"},{"issue":"1-3","key":"147_CR32","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0012-365X(94)90241-0","volume":"132","author":"V. Ramana Motakuri","year":"1994","unstructured":"Ramana Motakuri V., Scheinerman Edward R., Ullman Daniel (1994) Fractional isomorphism of graphs. Discrete Mathematics 132(1-3): 247\u2013265","journal-title":"Discrete Mathematics"},{"key":"147_CR33","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0024-3795(88)90054-7","volume":"111","author":"Schreck Helmut","year":"1988","unstructured":"Helmut Schreck, Gottfried Tinhofer (1988) A note on certain subpolytopes of the assignment polytope associated with circulant graphs. Linear Algebra and its Applications 111: 125\u2013134","journal-title":"Linear Algebra and its Applications"},{"key":"147_CR34","unstructured":"Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn & Karsten M. Borgwardt (2011). Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research 12, 2539\u20132561."},{"key":"147_CR35","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/BF02240204","volume":"36","author":"Tinhofer Gottfried","year":"1986","unstructured":"Gottfried Tinhofer (1986) Graph isomorphism and theorems of Birkhoff type. Computing 36: 285\u2013300","journal-title":"Computing"},{"issue":"3","key":"147_CR36","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0166-218X(88)90100-X","volume":"22","author":"Tinhofer Gottfried","year":"1989","unstructured":"Gottfried Tinhofer (1989) Strong tree-cographs are Birkhoff graphs. Discrete Applied Mathematics 22(3): 275\u2013288","journal-title":"Discrete Applied Mathematics"},{"issue":"2\u20133","key":"147_CR37","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0166-218X(91)90049-3","volume":"30","author":"Tinhofer Gottfried","year":"1991","unstructured":"Gottfried Tinhofer (1991) A note on compact graphs. Discrete Applied Mathematics 30(2\u20133): 253\u2013264","journal-title":"Discrete Applied Mathematics"},{"key":"147_CR38","unstructured":"Gottfried Tinhofer & Mikhail Klin (1999). Algebraic combinatorics in mathematical chemistry. Methods and algorithms III. Graph invariants and stabilization methods. Technical Report TUM-M9902, Technische Universit\u00e4t M\u00fcnchen."},{"issue":"1\u20133","key":"147_CR39","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/S0012-365X(99)00381-7","volume":"220","author":"Tyshkevich Regina","year":"2000","unstructured":"Regina Tyshkevich (2000) Decomposition of graphical sequences and unigraphs. Discrete Mathematics 220(1\u20133): 201\u2013238 Gabriel Valiente (2002). Algorithms on trees and graphs. Springer.","journal-title":"Discrete Mathematics"},{"issue":"5","key":"147_CR40","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1007\/s10114-004-0485-1","volume":"21","author":"Li PingWang&Jiong Sheng","year":"2005","unstructured":"PingWang&Jiong Sheng Li (2005) On compact graphs. Acta Mathematica Sinica 21(5): 1087\u20131092","journal-title":"Acta Mathematica Sinica"},{"key":"147_CR41","unstructured":"Boris Yu. Weisfeiler & Andrei A. Leman (1968). A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsia, Seriya 22 9, 12\u201316. In Russian."},{"key":"147_CR42","doi-asserted-by":"crossref","first-page":"150","DOI":"10.2307\/2371086","volume":"54","author":"Whitney Hassler","year":"1932","unstructured":"Hassler Whitney (1932) Congruent graphs and connectivity of graphs. American Journal of Mathematics 54: 150\u2013168","journal-title":"American Journal of Mathematics"},{"key":"147_CR43","unstructured":"Matan Ziv-Av (2013). Results of computer algebra calculations for triangle free strongly regular graphs. E-print http:\/\/www.math.bgu.ac.il\/~zivav\/math\/eqpart.pdf ."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0147-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0147-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0147-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,18]],"date-time":"2022-07-18T02:12:20Z","timestamp":1658110340000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0147-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,19]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["147"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0147-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,19]]}}}