Clique-width of path powers

DOI10.1016/J.DAM.2015.11.009MaRDI QIDQ266933zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Daniel Meister, Charis Papadopoulos, Udi Rotics

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

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

Recommendations

• A Complete Characterisation of the Linear Clique-Width of Path Powers
• Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
• Graph classes with and without powers of bounded clique-width
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• The NLC-width and clique-width for powers of graphs of bounded tree-width

Cites work

• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A Complete Characterisation of the Linear Clique-Width of Path Powers
• A characterisation of clique-width through nested partitions
• Algorithmic graph theory and perfect graphs
• Approximating clique-width and branch-width
• Clique-width is NP-complete
• Complement reducible graphs
• Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
• Graph Classes: A Survey
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graphs of linear clique-width at most 3
• Handle-rewriting hypergraph grammars
• Linear layouts measuring neighbourhoods in graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Minimal classes of graphs of unbounded clique-width
• On a disparity between relative cliquewidth and relative NLC-width
• On the clique-width of some perfect graph classes
• The relative clique-width of a graph
• Upper bounds to the clique width of graphs

Cited in

(9)

• Mim-width. III. Graph powers and generalized distance domination problems
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
• Graph classes with and without powers of bounded clique-width
• Clique width of partner limited graphs
• Clique-width of point configurations
• Clique-width of full bubble model graphs
• A Complete Characterisation of the Linear Clique-Width of Path Powers
• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q266933)