Line graphs of bounded clique-width
From MaRDI portal
Publication:2461201
DOI10.1016/j.disc.2007.01.020zbMath1128.05049OpenAlexW2015256259WikidataQ30051303 ScholiaQ30051303MaRDI QIDQ2461201
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
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (21)
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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- NLC2-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
This page was built for publication: Line graphs of bounded clique-width
