First-order complexity of subgraph isomorphism via Kneser graphs

DOI10.1134/S0001434621010041OpenAlexW3177772509MaRDI QIDQ2037624

Yanyan Li

Publication date: 8 July 2021

Published in: Mathematical Notes (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0001434621010041

zbMATH Keywords

Kneser graphEhrenfeucht gameinput-graphpattern-graph

Mathematics Subject Classification ID

Theory of computing (68Qxx) Graph theory (05Cxx) Enumerative combinatorics (05Axx)

Related Items (1)

On Ramsey numbers for arbitrary sequences of graphs

Cites Work

• Elements of finite model theory.
• Kneser's conjecture, chromatic number, and homotopy
• Maximum bipartite subgraphs of Kneser graphs
• On the diameter of Kneser graphs
• Connectivity of transitive graphs
• The descriptive complexity of subgraph isomorphism without numerics
• The strange logic of random graphs

This page was built for publication: First-order complexity of subgraph isomorphism via Kneser graphs