Clique-width of full bubble model graphs

DOI10.1016/j.dam.2014.12.001zbMath1311.05154arXiv1306.2114OpenAlexW2085968239MaRDI QIDQ2341723

Daniel Meister, Udi Rotics

Publication date: 28 April 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.2114

zbMATH Keywords

characterisationforbidden induced subgraphspolynomial timeclique-widthproper interval graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (2)

On the maximum cardinality cut problem in proper interval graphs and related graph classes ⋮ \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited

Cites Work

• Unnamed Item
• Clique-width of path powers
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• Clique-width with an inactive label
• Algorithmic graph theory and perfect graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• A characterisation of clique-width through nested partitions
• Optimal greedy algorithms for indifference graphs
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• The relative clique-width of a graph
• A new representation of proper interval graphs with an application to clique-width
• Clique-Width is NP-Complete
• Exploiting Restricted Linear Structure to Cope with the Hardness of Clique-Width
• Graph Classes: A Survey
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES

This page was built for publication: Clique-width of full bubble model graphs