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

DOI10.1016/j.dam.2007.03.014zbMath1129.68051OpenAlexW2019673912WikidataQ62046065 ScholiaQ62046065MaRDI QIDQ2383546

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

polynomialcoloringclique-widthpower graphNLC-width

Mathematics Subject Classification ID

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

Related Items

Complexity and Algorithms for Well-Structured k-SAT Instances ⋮ Graph classes with and without powers of bounded clique-width ⋮ Compact labelings for efficient first-order model-checking ⋮ Computing square roots of trivially perfect and threshold graphs ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ The NLC-width and clique-width for powers of graphs of bounded tree-width ⋮ Optimal centrality computations within bounded clique-width graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(k\)-NLC graphs and polynomial algorithms
• Edge dominating set and colorings on graphs with fixed clique-width
• Upper bounds to the clique width of graphs
• Approximating clique-width and branch-width
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• On the Relationship Between Clique-Width and Treewidth
• Graph-Theoretic Concepts in Computer Science

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