Well-quasi-ordering versus clique-width: new results on bigenic classes
From MaRDI portal
(Redirected from Publication:722586)
Abstract: Daligault, Rao and Thomass'e asked whether a hereditary class of graphs well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev recently showed that this is not true for classes defined by infinitely many forbidden induced subgraphs. However, in the case of finitely many forbidden induced subgraphs the question remains open and we conjecture that in this case the answer is positive. The conjecture is known to hold for classes of graphs defined by a single forbidden induced subgraph , as such graphs are well-quasi-ordered and are of bounded clique-width if and only if is an induced subgraph of . For bigenic classes of graphs, i.e. ones defined by two forbidden induced subgraphs, there are several open cases in both classifications. In the present paper we obtain a number of new results on well-quasi-orderability of bigenic classes, each of which supports the conjecture.
Recommendations
- Well-quasi-ordering versus clique-width: new results on bigenic classes
- Well-quasi-ordering versus clique-width
- Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation
- Well-quasi-ordering does not imply bounded clique-width
- Two forbidden induced subgraphs and well-quasi-ordering
Cites work
- scientific article; zbMATH DE number 2044928 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Approximating clique-width and branch-width
- Bounding clique-width via perfect graphs
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- Clique-width and edge contraction
- Clique-width and well-quasi-ordering of triangle-free graph classes
- Colouring diamond-free graphs
- Edge dominating set and colorings on graphs with fixed clique-width
- GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
- Graph minors. IV: Tree-width and well-quasi-ordering
- Graph minors. XX: Wagner's conjecture
- Induced subgraphs and well‐quasi‐ordering
- Labelled induced subgraphs and well-quasi-ordering
- Linear time solvable optimization problems on graphs of bounded clique-width
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- On the structure of (\(P_{5}\),\,gem)-free graphs
- Ordering by Divisibility in Abstract Algebras
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- The theory of well-quasi-ordering: a frequently discovered concept
- Two forbidden induced subgraphs and well-quasi-ordering
- Upper bounds to the clique width of graphs
- Well-quasi-order of relabel functions
- Well-quasi-ordering does not imply bounded clique-width
- Well-quasi-ordering versus clique-width: new results on bigenic classes
- Well-structured transition systems everywhere!
Cited in
(7)- Clique-width and well-quasi-ordering of triangle-free graph classes
- Well-quasi-ordering versus clique-width
- Well-quasi-ordering versus clique-width: new results on bigenic classes
- Clique-width and well-quasi-ordering of triangle-free graph classes
- Well-quasi-ordering does not imply bounded clique-width
- Clique-width for graph classes closed under complementation
- Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation
This page was built for publication: Well-quasi-ordering versus clique-width: new results on bigenic classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722586)
