On the Clique-Width of Unigraphs
share
Clique-width is a well-studied graph parameter. For graphs of bounded clique-width, many problems that are NP-hard in general can be polynomial-time solvable. The fact motivates many studies to investigate whether the clique-width of graphs in a certain class is bounded or not. We focus on unigraphs, that is, graphs uniquely determined by their degree sequences up to isomorphism. We show that every unigraph has clique-width at most 5. It follows that many problems that are NP-hard in general are polynomial-time solvable for unigraphs.
READ FULL TEXT