On powers of graphs of bounded NLC-width (clique-width)

DOI10.1016/J.DAM.2007.03.014MaRDI QIDQ2383546zbMATH OpenOpenAlexWikidataFDO

Authors Karol Suchan, Ioan Todinca

Publication date 19 September 2007

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

Full work available at URL https://doi.org/10.1016/j.dam.2007.03.014

zbMATH Keywords

clique-widthcoloringNLC-widthpolynomialpower graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Coloring powers of graphs of bounded clique-width.
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• On a disparity between relative cliquewidth and relative NLC-width
• NLC\(_{2}\)-decomposition in polynomial time

Cites work

• \(k\)-NLC graphs and polynomial algorithms
• Approximating clique-width and branch-width
• Coloring powers of graphs of bounded clique-width.
• Edge dominating set and colorings on graphs with fixed clique-width
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• scientific article; zbMATH DE number 1500531 (Why is no real title available?)
• On the clique-width of some perfect graph classes
• On the Relationship Between Clique-Width and Treewidth
• Upper bounds to the clique width of graphs

Cited in

(14)

• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Optimal centrality computations within bounded clique-width graphs
• Mim-width. III. Graph powers and generalized distance domination problems
• Computing square roots of trivially perfect and threshold graphs
• Complexity and Algorithms for Well-Structured k-SAT Instances
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• A Complete Characterisation of the Linear Clique-Width of Path Powers
• scientific article; zbMATH DE number 2044940 (Why is no real title available?)
• The behavior of clique-width under graph operations and graph transformations
• Coloring powers of graphs of bounded clique-width.
• Compact labelings for efficient first-order model-checking
• Fast FPT-approximation of branchwidth
• Comparing width parameters on graph classes
• Graph classes with and without powers of bounded clique-width

This page was built for publication: On powers of graphs of bounded NLC-width (clique-width)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2383546)