Geodesic
First-Order Complexity of Subgraph Isomorphism via Kneser Graphs
Matematičeskie zametki, Tome 109 (2021) no. 1, pp. 36-46.

Voir la notice de l'article provenant de la source Math-Net.Ru

The problem of finding the least number of variables of a first-order formula expressing the statement that an input-graph contains a subgraph isomorphic to a given pattern-graph is studied. Input-graphs of sufficiently high connectivity are considered. This problem has previously been solved for all pattern-graphs on four vertices except the simple cycle and the diamond graph. In the paper, this number is found for the two remaining graphs.
Keywords: Kneser graph, input-graph, pattern-graph, Ehrenfeucht game. 
@article{MZM_2021_109_1_a3,
     author = {V. A. Voronov and E. A. Dergachev and M. E. Zhukovskii and A. M. Neopryatnaya},
     title = {First-Order {Complexity} of {Subgraph} {Isomorphism} via {Kneser} {Graphs}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {36--46},
     publisher = {mathdoc},
     volume = {109},
     number = {1},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2021_109_1_a3/}
}
TY  - JOUR
AU  - V. A. Voronov
AU  - E. A. Dergachev
AU  - M. E. Zhukovskii
AU  - A. M. Neopryatnaya
TI  - First-Order Complexity of Subgraph Isomorphism via Kneser Graphs
JO  - Matematičeskie zametki
PY  - 2021
SP  - 36
EP  - 46
VL  - 109
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2021_109_1_a3/
LA  - ru
ID  - MZM_2021_109_1_a3
ER  - 
%0 Journal Article
%A V. A. Voronov
%A E. A. Dergachev
%A M. E. Zhukovskii
%A A. M. Neopryatnaya
%T First-Order Complexity of Subgraph Isomorphism via Kneser Graphs
%J Matematičeskie zametki
%D 2021
%P 36-46
%V 109
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2021_109_1_a3/
%G ru
%F MZM_2021_109_1_a3
V. A. Voronov; E. A. Dergachev; M. E. Zhukovskii; A. M. Neopryatnaya. First-Order Complexity of Subgraph Isomorphism via Kneser Graphs. Matematičeskie zametki, Tome 109 (2021) no. 1, pp. 36-46. http://geodesic.mathdoc.fr/item/MZM_2021_109_1_a3/

[1] N. K. Vereschagin, A. Shen, Yazyki i ischisleniya, MTsNMO, M., 2000

[2] L. Libkin, Elements of Finite Model Theory, Springer-Verlag, Berlin, 2004 | MR | Zbl

[3] O. Verbitsky, M. Zhukovskii, “he descriptive complexity of subgraph isomorphism without numerics”, Theory Comput. Syst., 63:4 (2019), 902–921 | DOI | MR | Zbl

[4] J. Spencer, The Strange Logic of Random Graphs, Algorithms Combin., 22, Springer-Verlag, Berlin, 2001 | MR | Zbl

[5] L. Lovász, “Kneser's conjecture, chromatic number, and homotopy”, J. Combin. Theory Ser. A, 25:3 (1978), 319–324 | DOI | MR | Zbl

[6] M. E. Watkins, “Connectivity of transitive graphs”, J. Combinatorial Theory, 8 (1970), 23–29 | DOI | MR | Zbl

[7] M. Valencia-Pabon, J. C. Vera, “On the diameter of Kneser graphs”, Discrete Math., 305:1-3 (2005), 383–385 | DOI | MR | Zbl

[8] S. Poljak, Z. Tuza, “Maximum bipartite subgraphs of Kneser graphs”, Graphs Combin., 3:2 (1987), 191–199 | DOI | MR | Zbl