2011/04/20 by Ling-Ju Hung, Hung, Ling-Ju, Ton Kloks +4
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1104.3917
arxiv created 2011/04/20 · openalex publication_date 2011/04/20 · arxiv updated 2015/03/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let k be a natural number. We introduce k-threshold graphs. We show that there exists an O(n3) algorithm for the recognition of k-threshold graphs for each natural number k. k-Threshold graphs are characterized by a finite collection of forbidden induced subgraphs. For the case k=2 we characterize the partitioned 2-threshold graphs by forbidden induced subgraphs. We introduce restricted -, and special 2-threshold graphs. We characterize both classes by forbidden induced subgraphs. The restricted 2-threshold graphs coincide with the switching class of threshold graphs. This provides a decomposition theorem for the switching class of threshold graphs.