The Library
Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation
Tools
Tools
Tools
Atminas, Aistis, Lozin, Vadim V. and Razgon, Igor (2019) Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation. Journal of Combinatorics, 10 (2). pp. 327-337. doi:10.4310/JOC.2019.v10.n2.a8
|
PDF
WRAP-graphs-large-bicliques-well-quasi-induced-subgraph-Lozin-2018.pdf - Accepted Version - Requires a PDF viewer. Download (521Kb) | Preview |
Official URL: http://doi.org/10.4310/JOC.2019.v10.n2.a8
Abstract
Recently, Daligault, Rao and Thomass\'e asked in [3] if every hereditary class which is well-quasi-ordered by the induced subgraph relation is of bounded clique-width. There are two reasons why this questions is interesting. First, it connects two seemingly unrelated notions. Second, if the question is answered affirmatively, this will have a strong algorithmic consequence. In particular, this will mean (through the use of Courcelle theorem [2]), that any problem definable in Monadic Second Order Logic can be solved in a polynomial time on any class well-quasi-ordered by the induced subgraph relation. In the present paper, we answer this question affirmatively for graphs without large bicliques. Thus the above algorithmic consequence is true, for example, for classes of graphs of bounded degree.
| Item Type: | Journal Article | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||
| Divisions: | Faculty of Science > Mathematics | ||||||
| Library of Congress Subject Headings (LCSH): | Bipartite graphs | ||||||
| Journal or Publication Title: | Journal of Combinatorics | ||||||
| Publisher: | International Press | ||||||
| ISSN: | 1942-5600 | ||||||
| Official Date: | 25 January 2019 | ||||||
| Dates: |
|
||||||
| Date of first compliant deposit: | 10 September 2018 | ||||||
| Volume: | 10 | ||||||
| Number: | 2 | ||||||
| Page Range: | pp. 327-337 | ||||||
| DOI: | 10.4310/JOC.2019.v10.n2.a8 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| RIOXX Funder/Project Grant: |
|
||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
