@article{WL1968,
  author = {Weisfeiler, Boris and Leman, Andrei A.},
  title = {The Reduction of a Graph to Canonical Form and the Algebra Which Appears Therein},
  journal = {Nauchno-Technicheskaya Informatsiya, Series 2, no. 9},
  pages = {12--16},
  year = {1968},
  note = {In Russian. English translation by Grigory Ryabov},
  url = {https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf}
}

@article{CFI1992,
  author = {Cai, Jin-yi and F{\"u}rer, Martin and Immerman, Neil},
  title = {An Optimal Lower Bound on the Number of Variables for Graph Identification},
  journal = {Combinatorica},
  volume = {12},
  number = {4},
  pages = {389--410},
  year = {1992},
  doi = {10.1007/BF01305232},
  url = {https://people.cs.umass.edu/~immerman/pub/opt.pdf}
}

@article{AMRSSV2019,
  author = {Atserias, Albert and Man{\v c}inska, Laura and Roberson, David E. and {\v S}{\'a}mal, Robert and Severini, Simone and Varvitsiotis, Antonios},
  title = {Quantum and Non-Signalling Graph Isomorphisms},
  journal = {Journal of Combinatorial Theory, Series B},
  volume = {136},
  pages = {289--328},
  year = {2019},
  doi = {10.1016/j.jctb.2018.11.002},
  url = {https://www.cs.upc.edu/~atserias/papers/quantumisomorphism/quantumisomorphisms.pdf},
  note = {Author-hosted manuscript dated October 25, 2018}
}

@article{Grohe1999,
  author = {Grohe, Martin},
  title = {Equivalence in Finite-Variable Logics Is Complete for Polynomial Time},
  journal = {Combinatorica},
  volume = {19},
  number = {4},
  pages = {507--532},
  year = {1999},
  doi = {10.1007/s004939970004},
  url = {https://link.springer.com/article/10.1007/s004939970004}
}

@article{IP2001,
  author = {Impagliazzo, Russell and Paturi, Ramamohan},
  title = {On the Complexity of {$k$}-{SAT}},
  journal = {Journal of Computer and System Sciences},
  volume = {62},
  number = {2},
  pages = {367--375},
  year = {2001},
  doi = {10.1006/jcss.2000.1727},
  url = {https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_2001_jcss.pdf}
}

@article{IPZ2001,
  author = {Impagliazzo, Russell and Paturi, Ramamohan and Zane, Francis},
  title = {Which Problems Have Strongly Exponential Complexity?},
  journal = {Journal of Computer and System Sciences},
  volume = {63},
  number = {4},
  pages = {512--530},
  year = {2001},
  doi = {10.1006/jcss.2001.1774},
  url = {https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturiZane_2001_jcss.pdf}
}

@article{Dvorak2010,
  author = {Dvo{\v r}{\'a}k, Zden{\v e}k},
  title = {On Recognizing Graphs by Numbers of Homomorphisms},
  journal = {Journal of Graph Theory},
  volume = {64},
  number = {4},
  pages = {330--342},
  year = {2010},
  doi = {10.1002/jgt.20461},
  url = {https://onlinelibrary.wiley.com/doi/10.1002/jgt.20461}
}

@phdthesis{Berkholz2014,
  author = {Berkholz, Christoph},
  title = {Lower Bounds for Heuristic Algorithms},
  school = {RWTH Aachen University},
  year = {2014},
  note = {Electronic publication 2015},
  url = {https://publications.rwth-aachen.de/record/462250/files/462250.pdf}
}

@inproceedings{DGR2018,
  author = {Dell, Holger and Grohe, Martin and Rattan, Gaurav},
  title = {{Lov{\'a}sz Meets Weisfeiler and Leman}},
  booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  series = {Leibniz International Proceedings in Informatics},
  volume = {107},
  pages = {40:1--40:14},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  year = {2018},
  doi = {10.4230/LIPIcs.ICALP.2018.40},
  url = {https://arxiv.org/abs/1802.08876v2},
  note = {Full version with Appendix B: arXiv:1802.08876v2}
}

@article{BN2023,
  author = {Berkholz, Christoph and Nordstr{\"o}m, Jakob},
  title = {Near-Optimal Lower Bounds on Quantifier Depth and {Weisfeiler--Leman} Refinement Steps},
  journal = {Journal of the ACM},
  volume = {70},
  number = {5},
  pages = {32:1--32:32},
  year = {2023},
  doi = {10.1145/3195257},
  url = {https://jakobnordstrom.se/docs/publications/QuantifierDepthWeisfeilerLeman_JACM.pdf}
}

@article{GLNS2025,
  author = {Grohe, Martin and Lichter, Moritz and Neuen, Daniel and Schweitzer, Pascal},
  title = {Compressing {CFI} Graphs and Lower Bounds for the {Weisfeiler--Leman} Refinements},
  journal = {Journal of the ACM},
  volume = {72},
  number = {3},
  pages = {21:1--21:27},
  year = {2025},
  doi = {10.1145/3727978},
  url = {https://arxiv.org/abs/2308.11970v2},
  note = {Conference version appeared at FOCS 2023}
}

@inproceedings{LRS2025,
  author = {Lichter, Moritz and Ra{\ss}mann, Simon and Schweitzer, Pascal},
  title = {Computational Complexity of the {Weisfeiler--Leman} Dimension},
  booktitle = {33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)},
  series = {Leibniz International Proceedings in Informatics},
  volume = {326},
  pages = {13:1--13:22},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  year = {2025},
  doi = {10.4230/LIPIcs.CSL.2025.13},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.13}
}

@misc{DN2026,
  author = {D{\"o}ring, Simon and Neuen, Daniel},
  title = {The Classical {Weisfeiler--Leman} Algorithm Stabilizes in {$O(n)$} Rounds},
  year = {2026},
  eprint = {2609.17364},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  note = {Preprint, version 1, 15 September 2026},
  url = {https://arxiv.org/abs/2609.17364v1}
}

@article{Roberson2026,
  author = {Roberson, David E.},
  title = {Oddomorphisms and Homomorphism Indistinguishability over Graphs of Bounded Degree},
  journal = {Journal of Combinatorial Theory, Series B},
  volume = {181},
  pages = {1--61},
  year = {2026},
  doi = {10.1016/j.jctb.2026.07.003},
  note = {Preprint: arXiv:2206.10321v1 (2022)},
  url = {https://arxiv.org/abs/2206.10321v1}
}

@misc{CompanionUnconditional,
  author = {{OpenAI}},
  title = {{Unconditional time lower bounds for Weisfeiler--Leman equivalence}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Unconditional-time-lower-bounds-for-Weisfeiler-Leman-equivalence-September-25-2026/paper.pdf}{OAI:Unconditional-time-lower-bounds-for-Weisfeiler-Leman-equivalence-September-25-2026}},
  year = {2026}
}

@misc{NS2026,
  author = {Neuen, Daniel and Seppelt, Tim},
  title = {Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs},
  year = {2026},
  eprint = {2601.18602},
  archivePrefix = {arXiv},
  primaryClass = {math.CO},
  note = {Version 2, 10 September 2026},
  url = {https://arxiv.org/abs/2601.18602v2}
}