Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419285 | Discrete Applied Mathematics | 2015 | 12 Pages |
Abstract
Clique-width of graphs is defined algebraically through operations on graphs with vertex labels. We characterise the clique-width in a combinatorial way by means of partitions of the vertex set, using trees of nested partitions where partitions are ordered bottom-up by refinement. We show that the correspondences in both directions, between combinatorial partition trees and algebraic terms, preserve the tree structures and that they are computable in polynomial time. We apply our characterisation to linear clique-width. And we relate our characterisation to a clique-width characterisation by Heule and Szeider that is used to reduce the clique-width decision problem to a satisfiability problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Bruno Courcelle, Pinar Heggernes, Daniel Meister, Charis Papadopoulos, Udi Rotics,