A local characterization of bounded clique-width for line graphs

DOI10.1016/J.DISC.2006.07.004MaRDI QIDQ868337zbMATHOpenAlexFDO

Authors Frank Gurski, Egon Wanke

Publication date 2 March 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.07.004

zbMATH Keywords

NLC-widthco-gem-free line graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Recommendations

• Line graphs of bounded clique-width
• Graphs of linear clique-width at most 3
• Graph-Theoretic Concepts in Computer Science
• Linear clique-width for hereditary classes of cographs
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs

Cites work

• scientific article; zbMATH DE number 1953082 (Why is no real title available?)
• scientific article; zbMATH DE number 1472167 (Why is no real title available?)
• Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
• Fundamentals of Computation Theory
• GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Graph-Theoretic Concepts in Computer Science
• Linear time solvable optimization problems on graphs of bounded clique-width
• Monadic second-order evaluations on tree-decomposable graphs
• On the relationship between NLC-width and linear NLC-width
• Upper bounds to the clique width of graphs
• \(k\)-NLC graphs and polynomial algorithms

Cited in

(5)

• Graph-Theoretic Concepts in Computer Science
• A Complete Characterisation of the Linear Clique-Width of Path Powers
• A Local Strengthening of Reed's $\omega$, $\Delta$, $\chi$ Conjecture for Quasi-line Graphs
• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• Line graphs of bounded clique-width

This page was built for publication: A local characterization of bounded clique-width for line graphs

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