Graph Operations on Clique-Width Bounded Graphs

Abstract

Clique-width is a well-known graph parameter. Many NP-hard graph problems admit polynomial-time solutions when restricted to graphs of bounded clique-width. The same holds for NLC-width. In this paper we study the behavior of clique-width and NLC-width under various graph operations and graph transformations. We give upper and lower bounds for the clique-width and NLC-width of the modified graphs in terms of the clique-width and NLC-width of the involved graphs.

30 pages, to appear in "Theory of Computing Systems"

References in corpus (1)

• NLC-2 graph recognition and isomorphism

Cited by in corpus (6)

• Clique-Width for Hereditary Graph Classes
• Bounding the Mim-Width of Hereditary Graph Classes
• List $k$-Colouring $P_t$-Free Graphs: a Mim-width Perspective
• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
• Bounds on the Twin-Width of Product Graphs
• Clique-Width: Harnessing the Power of Atoms