Well-quasi-ordering versus clique-width: new results on bigenic classes
From MaRDI portal
Publication:722586
DOI10.1007/S11083-017-9430-7zbMATH Open1404.05179arXiv1611.03671OpenAlexW2733323637WikidataQ59614166 ScholiaQ59614166MaRDI QIDQ722586FDOQ722586
Authors: Konrad Dabrowski, Vadim Lozin, Daniël Paulusma 
Publication date: 27 July 2018
Published in: Order (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1611.03671
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
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Graph minors. XX: Wagner's conjecture
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Approximating clique-width and branch-width
- Well-structured transition systems everywhere!
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- The theory of well-quasi-ordering: a frequently discovered concept
- Two forbidden induced subgraphs and well-quasi-ordering
- Induced subgraphs and well‐quasi‐ordering
- Ordering by Divisibility in Abstract Algebras
- On the structure of (\(P_{5}\),\,gem)-free graphs
- Edge dominating set and colorings on graphs with fixed clique-width
- GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- Title not available (Why is that?)
- Graph minors. IV: Tree-width and well-quasi-ordering
- Clique-width and edge contraction
- Well-quasi-order of relabel functions
- Bounding clique-width via perfect graphs
- Well-quasi-ordering versus clique-width: new results on bigenic classes
- Well-quasi-ordering does not imply bounded clique-width
- Colouring diamond-free graphs
- Clique-width and well-quasi-ordering of triangle-free graph classes
- Labelled induced subgraphs and well-quasi-ordering
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)
