2012/10/30 by M. Chang, Maw‐Shang Chang, Ling-Ju Hung +9
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1210.8365
arxiv created 2012/10/30 · openalex publication_date 2012/10/30 · arxiv updated 2012/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The GG-width of a class of graphs GG is defined as follows. A graph G has GG-width k if there are k independent sets N1,...,Nk in G such that G can be embedded into a graph H in GG such that for every edge e in H which is not an edge in G, there exists an i such that both endpoints of e are in Ni. For the class TH of threshold graphs we show that TH-width is NP-complete and we present fixed-parameter algorithms. We also show that for each k, graphs of TH-width at most k are characterized by a finite collection of forbidden induced subgraphs.