First-order complexity of subgraph isomorphism via Kneser graphs
type: Item
instance of: scholarly article
title: First-order complexity of subgraph isomorphism via Kneser graphs
DOI: 10.1134/S0001434621010041
author: Yanyan Li
published in: Mathematical Notes
publication date: 2021-07-08T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
Mathematics Subject Classification ID: 05Cxx
Mathematics Subject Classification ID: 05Axx
zbMATH DE Number: 7369674
zbMATH Keywords: Kneser graph
zbMATH Keywords: input-graph
zbMATH Keywords: pattern-graph
zbMATH Keywords: Ehrenfeucht game
MaRDI profile type: Publication
cites work: Elements of finite model theory.
cites work: The descriptive complexity of subgraph isomorphism without numerics
cites work: The strange logic of random graphs
cites work: Kneser's conjecture, chromatic number, and homotopy
cites work: Connectivity of transitive graphs
cites work: On the diameter of Kneser graphs
cites work: Maximum bipartite subgraphs of Kneser graphs
full work available at URL: s0001434621010041
OpenAlex ID: W3177772509
description: scientific article; zbMATH DE number 7369674