Live briefing
Everything about Clique-width
Measure of graph complexity
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)) Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Clique-widthA 5-minute orientation
- Skim a recent paper: Optimal Centrality Computations Within Bounded Clique-Width GraphsInfluential work since 2022
- Read the landmark paper: Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-WidthCited 600 times
- Go sideways: Distance-hereditary graphA closely related topic
- Go sideways: CographA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width
Upper bounds to the clique width of graphs
Approximating clique-width and branch-width
On the Relationship Between Clique-Width and Treewidth
Clique-Width is NP-Complete
Recent developments on graphs of bounded clique-width
Approximating rank-width and clique-width quickly
Counting truth assignments of formulas of bounded tree-width or clique-width
🆕 Influential since 2022
Optimal Centrality Computations Within Bounded Clique-Width Graphs
Uncountably Many Minimal Hereditary Classes of Graphs of Unbounded Clique-Width
Succinct data structures for bounded clique-width graphs
Conflict-Free Coloring: Graphs of Bounded Clique-Width and Intersection Graphs
A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width
📚 Books worth reading
Open Library didn't respond; try again in a moment.
🔗 Related topics
- Distance-hereditary graph In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances…
- Cograph In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation…
- Treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest…
- Courcelle's theorem In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs…
- Leaf power In the mathematical area of graph theory, a k-leaf power of a tree T is a graph G whose vertices are the leaves of T and whose edges connect pairs of leaves…
- Pathwidth In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number…
- Hadwiger number In graph theory, the Hadwiger number of an undirected graph G is the size of the largest complete graph that can be obtained by contracting edges of G…
- Logic of graphs In the mathematical fields of graph theory and finite model theory, the logic of graphs deals with formal specifications of graph properties using sentences…