MSOL partitioning problems on graphs of bounded treewidth and clique-width

DOI10.1016/j.tcs.2007.03.043zbMath1118.68107OpenAlexW2008361472MaRDI QIDQ884481

Michaël Rao

Publication date: 6 June 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.03.043

zbMATH Keywords

monadic second-order logictreewidthgraph algorithmsclique-widthvertex partitioning

Mathematics Subject Classification ID

Related Items (45)

Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs ⋮ On coloring a class of claw-free graphs. ⋮ Clique cycle-transversals in distance-hereditary graphs ⋮ On the structure of graphs without claw, \(4K_1\) and co-R ⋮ Vertex coloring of graphs with few obstructions ⋮ Vertex partitioning problems on graphs with bounded tree width ⋮ On some domination colorings of graphs ⋮ Colouring diamond-free graphs ⋮ Characterizations of \((4 K_1,C_4,C_5)\)-free graphs ⋮ Colouring square-free graphs without long induced paths. ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ A coloring algorithm for \(4 K_1\)-free line graphs ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs ⋮ Clique‐width: Harnessing the power of atoms ⋮ Coloring \((4K_1,C_4,C_6)\)-free graphs ⋮ Bounding clique-width via perfect graphs ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ Directed NLC-width ⋮ Classifying the clique-width of \(H\)-free bipartite graphs ⋮ Automata for the verification of monadic second-order graph properties ⋮ Graphs vertex-partitionable into strong cliques ⋮ Polynomial cases for the vertex coloring problem ⋮ \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth ⋮ On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width ⋮ Parameterized shifted combinatorial optimization ⋮ Well-quasi-ordering versus clique-width: new results on bigenic classes ⋮ Clique-width and well-quasi-ordering of triangle-free graph classes ⋮ Partitioning graphs into induced subgraphs ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Computations by fly-automata beyond monadic second-order logic ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ Bounds and fixed-parameter algorithms for weighted improper coloring ⋮ Nontrivial path covers of graphs: existence, minimization and maximization ⋮ Unnamed Item ⋮ The intersection of two vertex coloring problems ⋮ Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes ⋮ Square-Free Graphs with No Six-Vertex Induced Path ⋮ Colouring vertices of triangle-free graphs without forests ⋮ Colouring square-free graphs without long induced paths ⋮ On coloring a class of claw-free and hole-twin-free graphs ⋮ Revising Johnson's table for the 21st century ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ Tree Pivot-Minors and Linear Rank-Width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic uses of the Feferman-Vaught theorem
• The strong perfect graph theorem
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• The monadic theory of order
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Achromatic number is NP-complete for cographs and interval graphs
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Linear time solvable optimization problems on graphs of bounded clique-width
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• The first order properties of products of algebraic systems
• Easy problems for tree-decomposable graphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• On the Relationship Between Clique-Width and Treewidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: MSOL partitioning problems on graphs of bounded treewidth and clique-width