Edge dominating set and colorings on graphs with fixed clique-width

DOI10.1016/S0166-218X(02)00198-1zbMath1009.05103OpenAlexW2070790034MaRDI QIDQ1861574

Publication date: 9 March 2003

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00198-1

zbMATH Keywords

edge-coloring polynomial algorithms dominating set coloring clique-width edge-dominating set

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (74)

Characterizations for co-graphs defined by restricted NLC-width or clique-width operations ⋮ On coloring a class of claw-free graphs. ⋮ Polynomial algorithms for protein similarity search for restricted mRNA structures ⋮ List coloring in the absence of two subgraphs ⋮ On powers of graphs of bounded NLC-width (clique-width) ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ The computational complexity of dominating set problems for instances with bounded minors of constraint matrices ⋮ Colouring diamond-free graphs ⋮ Parameterized analysis and crossing minimization problems ⋮ Complexity classification of the edge coloring problem for a family of graph classes ⋮ Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem ⋮ 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 ⋮ Data reduction for graph coloring problems ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ Structure and algorithms for (cap, even hole)-free graphs ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Clique‐width: Harnessing the power of atoms ⋮ Graph classes with and without powers of bounded clique-width ⋮ Bounding clique-width via perfect graphs ⋮ Graphs of separability at most 2 ⋮ Polynomial-time recognition of clique-width $\leq 3$ graphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Unnamed Item ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ Unnamed Item ⋮ On the structure of (pan, even hole)‐free graphs ⋮ Directed NLC-width ⋮ Classifying the clique-width of $H$-free bipartite graphs ⋮ Unnamed Item ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Linear Clique‐Width for Hereditary Classes of Cographs ⋮ Obstructions for linear rank-width at most 1 ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ Latency-bounded target set selection in social networks ⋮ Minimal classes of graphs of unbounded clique-width ⋮ Graphs of Separability at Most Two: Structural Characterizations and Their Consequences ⋮ Line graphs of bounded clique-width ⋮ List $k$-colouring $P_t$-free graphs: a mim-width perspective ⋮ Computing the Chromatic Number Using Graph Decompositions via Matrix Rank ⋮ Solving some NP-complete problems using split decomposition ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ Recent developments on graphs of bounded clique-width ⋮ $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 ⋮ Approximating clique-width and branch-width ⋮ Boolean-width of graphs ⋮ Unnamed Item ⋮ Vertex disjoint paths on clique-width bounded graphs ⋮ On the Boolean-Width of a Graph: Structure and Applications ⋮ Well-quasi-ordering versus clique-width: new results on bigenic classes ⋮ Clique-width and well-quasi-ordering of triangle-free graph classes ⋮ Bounding Clique-Width via Perfect Graphs ⋮ An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Unnamed Item ⋮ Data Reduction for Graph Coloring Problems ⋮ Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Square-Free Graphs with No Six-Vertex Induced Path ⋮ Colouring square-free graphs without long induced paths ⋮ Boolean-Width of Graphs ⋮ Computing the chromatic number using graph decompositions via matrix rank ⋮ Digraphs of Bounded Width ⋮ Revising Johnson's table for the 21st century ⋮ On the relationship between NLC-width and linear NLC-width ⋮ Tree Pivot-Minors and Linear Rank-Width ⋮ Critical elements in combinatorially closed families of graph classes ⋮ The computational complexity of three graph problems for instances with bounded minors of constraint matrices ⋮ On algorithms for ($P_5$, gem)-free graphs ⋮ Equitable colorings of bounded treewidth graphs

Cites Work

This page was built for publication: Edge dominating set and colorings on graphs with fixed clique-width