2021/03/22 by Alexandr Kostochka, Mina Nahvi, Kostochka, Alexandr V. +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2103.12153
openalex publication_date 2021/03/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The (n-ℓ)-deck of an n-vertex graph is the multiset of subgraphs obtained from it by deleting ℓ vertices. A family of n-vertex graphs is ℓ-recognizable if every graph having the same (n-ℓ)-deck as a graph in the family is also in the family. We prove that the family of n-vertex graphs having no cycles is ℓ-recognizable when n≥2ℓ+1 (except for (n,ℓ)=(5,2)). It is known that this fails when n=2ℓ.