On first-order definitions of subgraph isomorphism properties
Tóm tắt
Let φ(F) be the property of containing (as a subgraph) an isomorphic copy of a graph F. It is easy to show that this property cannot be defined in a first-order language by a sentence with a quantifier depth (or variable width) strictly less than the number of vertices in F. Nevertheless, such a definition exists in some classes of graphs. Three classes of graphs are considered: connected graphs with a large number of vertices, graphs with large treewidth, and graphs with high connectivity.
Tài liệu tham khảo
N. K. Vereshchagin and A. Shen’, Languages and Calculi (MNTsMO, Moscow, 2000) [in Russian].
M. E. Zhukovskii and A. M. Raigorodskii, Russ. Math. Surv. 70 (1), 33–81 (2015).
R. Diestel, Graph Theory (Springer, New York, 2000).
O. Verbitsky and M. Zhukovskii, arXiv:1607.08067v3, 2017 (LNCS 10304, to appear in Proc. CSR 2017).
L. Libkin, Elements of Finite Model Theory (Springer, Berlin, 2004).
J. Nešetřil and S. Poljak, Comment. Math. Univ. Carol 26, 415–419 (1985).
F. L. Gall, Proceedings of ISSAC'14 (ACM, New York, 2014), pp. 296–303.
J. Chen, X. Huang, I. A. Kanj, and G. Xia, J. Comput. Syst. Sci. 72, 1346–1367 (2006).
B. Courcelle, Inf. Comput. 85, 12–75 (1990).
C. Chekuri and J. Chuzhoy, Proceedings of STOC'14 (New York, 2014), pp. 60–69.
M. McArtur, Logic Random Struct. 33, 53–63 (1997).
M. Zhukovskii, Discrete Math. 312, 1670–1688 (2012).