Characterizations for co-graphs defined by restricted NLC-width or clique-width operations

DOI10.1016/j.disc.2005.11.014zbMath1085.05055OpenAlexW1985956090MaRDI QIDQ819817

Frank Gurski

Publication date: 29 March 2006

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

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

zbMATH Keywords

clique-widththreshold graphsco-graphsNLCT-widthtrivially perfect

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Perfect graphs (05C17)

Related Items (12)

Characterizations for restricted graphs of NLC-width 2 ⋮ \(H\)-product of graphs, \(H\)-threshold graphs and threshold-width of graphs ⋮ Graphs of Linear Clique-Width at Most 3 ⋮ Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs ⋮ Linear Clique‐Width for Hereditary Classes of Cographs ⋮ Clique-width with an inactive label ⋮ A simple linear-time recognition algorithm for weakly quasi-threshold graphs ⋮ The complexity of the list homomorphism problem for graphs ⋮ Graphs of linear clique-width at most 3 ⋮ Linear layouts measuring neighbourhoods in graphs ⋮ Comparing linear width parameters for directed graphs ⋮ Linear rank-width and linear clique-width of trees

Cites Work

• Complement reducible graphs
• Trivially perfect graphs
• \(k\)-NLC graphs and polynomial algorithms
• Edge dominating set and colorings on graphs with fixed clique-width
• Threshold graphs and related topics
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Approximating clique-width and branch-width
• On the relationship between NLC-width and linear NLC-width
• A Linear Recognition Algorithm for Cographs
• The Comparability Graph of a Tree
• Dacey Graphs
• Graph Classes: A Survey
• NLC₂-DECOMPOSITION IN POLYNOMIAL TIME
• Graph-Theoretic Concepts in Computer Science
• LATIN 2004: Theoretical Informatics
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Characterizations for co-graphs defined by restricted NLC-width or clique-width operations