Clique-width of path powers

DOI10.1016/j.dam.2015.11.009zbMath1333.05221OpenAlexW2286033726MaRDI QIDQ266933

Daniel Meister, Udi Rotics, Pinar Heggernes, Charis Papadopoulos

Publication date: 7 April 2016

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

Full work available at URL: https://doi.org/10.1016/j.dam.2015.11.009

zbMATH Keywords

clique-widthforbidden induced subgraphs characterisationlinear-time computationproper interval graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Unnamed Item ⋮ Mim-width. III. Graph powers and generalized distance domination problems ⋮ Clique-width of full bubble model graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Minimal classes of graphs of unbounded clique-width
• Graphs of linear clique-width at most 3
• On a disparity between relative cliquewidth and relative NLC-width
• Complement reducible graphs
• Algorithmic graph theory and perfect graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• A characterisation of clique-width through nested partitions
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• Linear layouts measuring neighbourhoods in graphs
• The relative clique-width of a graph
• Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width
• Clique-Width is NP-Complete
• A Complete Characterisation of the Linear Clique-Width of Path Powers
• Graph Classes: A Survey
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES

This page was built for publication: Clique-width of path powers