Clique-width and well-quasi-ordering of triangle-free graph classes

DOI10.1016/j.jcss.2019.09.001zbMath1442.05184OpenAlexW2763059940WikidataQ127202508 ScholiaQ127202508MaRDI QIDQ5918202

Konrad K. Dabrowski, Daniël Paulusma, Vadim V. Lozin

Publication date: 29 November 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2019.09.001

zbMATH Keywords

well-quasi-orderingclique-widthforbidden induced subgraphhereditary graph class

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy, Bounding the mim‐width of hereditary graph classes, Clique‐width: Harnessing the power of atoms, Clique-Width for Graph Classes Closed under Complementation, Bounding the Mim-Width of Hereditary Graph Classes., Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure

Cites Work

• Unnamed Item
• Unnamed Item
• Boundary properties of well-quasi-ordered sets of graphs
• The disjoint paths problem in quadratic time
• The behavior of clique-width under graph operations and graph transformations
• Well-quasi-order of relabel functions
• Graph minors. XX: Wagner's conjecture
• Well-quasi-ordering versus clique-width: new results on bigenic classes
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Labelled induced subgraphs and well-quasi-ordering
• Classifying the clique-width of \(H\)-free bipartite graphs
• Recent developments on graphs of bounded clique-width
• Clique-width and the speed of hereditary properties
• Well-quasi-ordering versus clique-width
• A counterexample regarding labelled well-quasi-ordering
• Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
• Algorithmic analysis of programs with well quasi-ordered domains.
• Edge dominating set and colorings on graphs with fixed clique-width
• Graph minors. XIII: The disjoint paths problem
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Two forbidden induced subgraphs and well-quasi-ordering
• Graph isomorphism for \((H_1,H_2)\)-free graphs: an almost complete dichotomy
• Clique-width and edge contraction
• Colouring diamond-free graphs
• Well-quasi-ordering \(H\)-contraction-free graphs
• Bounding clique-width via perfect graphs
• Clique-width for 4-vertex forbidden subgraphs
• Approximating clique-width and branch-width
• Wohlquasigeordnete Klassen endlicher Graphen
• The theory of well-quasi-ordering: a frequently discovered concept
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Bipartite induced subgraphs and well-quasi-ordering
• Subgraphs and well‐quasi‐ordering
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION
• Induced subgraphs and well‐quasi‐ordering
• Ordering by Divisibility in Abstract Algebras
• Induced minors and well-quasi-ordering
• Clique-width and well-quasi-ordering of triangle-free graph classes
• Well-structured transition systems everywhere!