Clique-width and edge contraction

DOI10.1016/j.ipl.2013.09.012zbMath1329.05278arXiv1306.6168OpenAlexW2147653456MaRDI QIDQ2350597

No author found.

Publication date: 25 June 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.6168

zbMATH Keywords

graph algorithmsclique-widthrank-widthvertex-minoredge contractionmonadic second-order transduction

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Rank-width: algorithmic and structural results ⋮ Grammars and clique-width bounds from split decompositions ⋮ Bounding clique-width via perfect graphs ⋮ Induced minor free graphs: isomorphism and clique-width ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ Well-quasi-ordering versus clique-width: new results on bigenic classes ⋮ Clique-width and well-quasi-ordering of triangle-free graph classes ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes ⋮ A characterisation of clique-width through nested partitions ⋮ Tree Pivot-Minors and Linear Rank-Width

Cites Work

• Unnamed Item
• Unnamed Item
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• Graphs of linear clique-width at most 3
• Recent developments on graphs of bounded clique-width
• The rank-width of the square grid
• Monadic second-order definable graph transductions: a survey
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Parametrized complexity theory.
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• Multicut on Graphs of Bounded Clique-Width
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES

This page was built for publication: Clique-width and edge contraction