Line graphs of bounded clique-width

2007/02/17 by Frank Gurski, Egon Wanke · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Bounded function #Chordal graph #Clique #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Graph theory and applications #Independent set #Line graph #Mathematical analysis #Mathematics #Path (computing) #Pathwidth #Treewidth

paper · doi:10.1016/j.disc.2007.01.020

openalex publication_date 2007/02/17 · crossref created 2007/02/17 · crossref issued 2007/10/01 · crossref published 2007/10/01 · crossref published-print 2007/10/01 · crossref deposited 2019/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/03/10 · crossref indexed 2026/03/24

Citations

• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Upper bounds to the clique width of graphs
• A max m,n algorithm for determining the graph H from its line graph G
• A Linear Recognition Algorithm for Cographs
• Graph minors. I. Excluding a forest
• Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width
• Characterizations of derived graphs
• Complexity of Finding Embeddings in a k -Tree
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Congruent Graphs and the Connectivity of Graphs

Cited by

• Clique-width and induced topological minors
• The Behavior of Clique-Width under Graph Operations and Graph Transformations
• Pathwidth [wikipedia]