Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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 ISSN 1942-5600.

[img]
Preview
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

Request Changes to record.

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, Engineering and Medicine > 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:
DateEvent
25 January 2019Published
12 July 2018Accepted
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
Date of first compliant deposit: 10 September 2018
Date of first compliant Open Access: 10 April 2019
RIOXX Funder/Project Grant:
Project/Grant IDRIOXX Funder NameFunder ID
EP/L020408/1[EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
Open Access Version:
  • ArXiv

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us