Between clique-width and linear clique-width of bipartite graphs

DOI10.1016/J.DISC.2020.111926MaRDI QIDQ2185929zbMATH OpenOpenAlexFDO

Authors Bogdan Alecu, Mamadou Moustapha Kanté, Vadim Lozin, Victor Zamaraev

Publication date 8 June 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL http://wrap.warwick.ac.uk/136165/1/WRAP-Between-clique-width-linear-clique-width-bipartite-graph-Lozin-2020.pdf

zbMATH Keywords

\(L\)-critical graphbipartite cographboundary classbounded clique widthlinear clique-width

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• Linear clique-width for hereditary classes of cographs
• scientific article; zbMATH DE number 2191997
• The tree- and clique-width of bipartite graphs in special classes
• Classifying the clique-width of \(H\)-free bipartite graphs
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs

Cites work

• An attractive class of bipartite graphs
• Bi-complement reducible graphs
• Boundary properties of factorial classes of graphs
• Boundary properties of the satisfiability problems
• Boundary properties of well-quasi-ordered sets of graphs
• Bounding the clique-width of \(H\)-free split graphs
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• Chordal bipartite graphs of bounded tree- and clique-width
• Clique-width is NP-complete
• Graphs of linear clique-width at most 3
• scientific article; zbMATH DE number 4121438 (Why is no real title available?)
• scientific article; zbMATH DE number 2191997 (Why is no real title available?)
• Infinitely many minimal classes of graphs of unbounded clique-width
• Labelled induced subgraphs and well-quasi-ordering
• Linear clique-width for hereditary classes of cographs
• Linear clique-width of bi-complement reducible graphs
• Linear rank-width and linear clique-width of trees
• Linear time algorithm for computing a small biclique in graphs without long induced paths
• Minimal classes of graphs of unbounded clique-width
• On factorial properties of chordal bipartite graphs
• On the clique-width of some perfect graph classes
• On the relationship between NLC-width and linear NLC-width
• Quasi-threshold graphs
• THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
• The relative clique-width of a graph
• The vertex separation and search number of a graph
• Trivially perfect graphs
• Upper domination: towards a dichotomy through boundary properties

Cited in

(10)

• Clique width of partner limited graphs
• Linear clique-width for hereditary classes of cographs
• THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
• Bipartite graphs of large clique-width
• Tree pivot-minors and linear rank-width
• A new graph construction of unbounded clique-width
• scientific article; zbMATH DE number 2191997 (Why is no real title available?)
• A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width
• Critical properties of bipartite permutation graphs
• An overview of universal obstructions for graph parameters

This page was built for publication: Between clique-width and linear clique-width of bipartite graphs

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