In graph theory, the clique-width of a graph G is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be small for dense graphs. It is defined as the minimum number of labels needed to construct G by means of the following 4 operations : Creation of a new vertex v with label i (denoted by i(v)) Disjoint union of two labeled graphs G and H (denoted by ) Joining by an edge every vertex labeled i to every vertex labeled j (denoted by η(i,j)), where i ≠ j Renaming label i to label j (denoted by ρ(i,j)) Graphs of bounded clique-width include the cographs and distance-hereditary graphs. Although it is NP-hard to compute the clique-width when it is unbounded, and unknown whether it can be computed in polynomial time when it is bounded, efficient approximation algorithms for clique-width are known. Based on these algorithms and on Courcelle's theorem, many graph optimization problems that are NP-hard for arbitrary graphs can be solved or approximated quickly on the graphs of bounded clique-width. The construction sequences underlying the concept of clique-width were formulated by Courcelle, Engelfriet, and Rozenberg in 1990 and by . The name "clique-width" was used for a different concept by . By 1993, the term already had its present meaning. Cographs are exactly the graphs with clique-width at most 2. Every distance-hereditary graph has clique-width at most 3. However, the clique-width of unit interval graphs is unbounded (based on their grid structure). Similarly, the clique-width of bipartite permutation graphs is unbounded (based on similar grid structure). Based on the characterization of cographs as the graphs with no induced subgraph isomorphic to a path with four vertices, the clique-width of many graph classes defined by forbidden induced subgraphs has been classified. Other graphs with bounded clique-width include the k-leaf powers for bounded values of k; these are the induced subgraphs of the leaves of a tree T in the graph power Tk.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.