Upper bounds to the clique width of graphs

By Bruno Courcelle, Stephan Olariu. Discrete Applied Mathematics, 2000

668 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

On H-immersions (2008, neutral): “Courcelle and Olariu [2] showed that cliquewidth is at most 2 + 1 and later Corneil and Rotices [1] that clique-width is at most 3 · 2twd(G)−1.”
A bound on the chromatic number using the longest odd cycle length (2007, background): “The interest began when these graphs arose in connection with a study on graph grammars [10], and it came”
Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width (2000, methodology): “We recall the notions of graph operations and clique-width presented in [ CO ].”
The n-ordered graphs: A new graph class (2009, methodology): “Rank-width is a graph width parameter, like tree-width, introduced by Oum and Seymour [18] to investigate clique-width [5].”
Approximating clique-width and branch-width (2006, background): “The notion of clique-width was first introduced by Courcelle and Olariu [7].”
Graphs of bounded rank-width (2005, neutral): “Every graph G of tree-width at most k has clique-width at most O(2 k ) (Corneil and Rotics [11], Courcelle and Olariu [19]), and for such graphs (for k fixed) the clique-width of G can be determined in linear time (Espelage et al. [24]).”