Clique-width of partner-limited graphs

✍ Scribed by Jean-Marie Vanherpe

• Book ID: 104113353
• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 371 KB
• Volume: 276
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(03)00295-4

✦ Synopsis

The clique-width of a graph G is the minimum number of labels that are required for deÿning G by an expression based on graph operations using vertex labels. The partner-limited graphs (PL-graphs for short) are deÿned to be graphs with a limited number of P4's. We prove that PL-graphs are of bounded clique-width. It follows that a large number of optimization problems have polynomial solutions for this family of graphs.