Lozin, Vadim V., Razgon, Igor and Zamaraev, Viktor (2018) Well-quasi-ordering versus clique-width. Journal of Combinatorial Theory, Series B, 130 . pp. 1-18. doi:10.1016/j.jctb.2017.09.012

Preview

PDF WRAP-well-quasi-ordering-versus-clique-width-Lozin-2017.pdf - Accepted Version - Requires a PDF viewer. Download (627Kb) | Preview

Request Changes to record.

Abstract

Does well-quasi-ordering by induced subgraphs imply bounded clique-width for hereditary classes? This question was asked by Daligault, Rao, and Thomassé [7]. We answer this question negatively by presenting a hereditary class of graphs of unbounded clique-width which is well-quasi-ordered by the induced subgraph relation. We also show that graphs in our class have at most logarithmic clique-width and that the number of minimal forbidden induced subgraphs for our class is infinite. These results lead to a conjecture relaxing the above question and to a number of related open questions connecting well-quasi-ordering and clique-width.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Mathematics
Library of Congress Subject Headings (LCSH):	Graph theory
Journal or Publication Title:	Journal of Combinatorial Theory, Series B
Publisher:	Academic Press
ISSN:	0095-8956
Official Date:	May 2018
Dates:	Date Event May 2018 Published 2 October 2017 Available 25 September 2017 Accepted
Volume:	130
Page Range:	pp. 1-18
DOI:	10.1016/j.jctb.2017.09.012
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Funder:	Engineering and Physical Sciences Research Council (EPSRC)
Grant number:	EP/L020408/1

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads