Line graphs of bounded clique-width

DOI10.1016/j.disc.2007.01.020zbMath1128.05049OpenAlexW2015256259WikidataQ30051303 ScholiaQ30051303MaRDI QIDQ2461201

Frank Gurski, Egon Wanke

Publication date: 27 November 2007

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2007.01.020

zbMATH Keywords

incidence graphsline graphsclique-widthtree-widthNLC-width

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Characterizations of \((4 K_1,C_4,C_5)\)-free graphs, Complexity classification of the edge coloring problem for a family of graph classes, Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem, Parameterized edge Hamiltonicity, Bounding the Clique-Width of H-free Chordal Graphs, Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs, Graph classes with and without powers of bounded clique-width, Polynomial-time recognition of clique-width \(\leq 3\) graphs, Compact labelings for efficient first-order model-checking, Tree-Width and Optimization in Bounded Degree Graphs, Unnamed Item, Directed NLC-width, Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis, Computing the clique-width of cactus graphs, The behavior of clique-width under graph operations and graph transformations, Recent developments on graphs of bounded clique-width, Excluding a bipartite circle graph from line graphs, Bounding Clique-Width via Perfect Graphs, Graph functionality, The intersection of two vertex coloring problems, Critical elements in combinatorially closed families of graph classes

Cites Work

• Graph minors. I. Excluding a forest
• \(k\)-NLC graphs and polynomial algorithms
• Chordal bipartite graphs of bounded tree- and clique-width
• On simple characterizations of k-trees
• Edge dominating set and colorings on graphs with fixed clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Approximating clique-width and branch-width
• Vertex disjoint paths on clique-width bounded graphs
• On the relationship between NLC-width and linear NLC-width
• Clique-width minimization is NP-hard
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• A Linear Recognition Algorithm for Cographs
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• An algebraic theory of graph reduction
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Handbook of Graph Grammars and Computing by Graph Transformation
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• NLC₂-DECOMPOSITION IN POLYNOMIAL TIME
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• On the Relationship Between Clique-Width and Treewidth
• Characterizations of derived graphs
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science
• LATIN 2004: Theoretical Informatics
• Graph-Theoretic Concepts in Computer Science
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item