Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes

Dreier, Jan; Mählmann, Nikolas; Toruńczyk, Szymon

doi:10.1145/3618260.3649739

by Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk

Reference:

Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph ClassesJan Dreier, Nikolas Mählmann, Szymon ToruńczykProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1550–1560, 2024, Association for Computing Machinery.

Bibtex Entry:

@inproceedings{dreier2024flipbreakability,
author = {Dreier, Jan and M\"{a}hlmann, Nikolas and Toru\'{n}czyk, Szymon},
title = {Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes},
year = {2024},
isbn = {9798400703836},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {10.1145/3618260.3649739">https://doi.org/10.1145/3618260.3649739},
pdf={https://arxiv.org/pdf/2403.15201.pdf},
doi = {10.1145/3618260.3649739},
booktitle = {Proceedings of the 56th Annual ACM Symposium on Theory of Computing},
pages = {1550–1560},
numpages = {11},
keywords = {Monadically dependent, algorithmic model theory, first-order model checking, monadically NIP, structural graph theory},
location = {Vancouver, BC, Canada},
series = {STOC 2024}
}