The Open UniversitySkip to content

Well-quasi-ordering and finite distinguishing number

Atminas, Aistis and Brignall, Robert (2019). Well-quasi-ordering and finite distinguishing number. Journal of Graph Theory (In Press).

Google Scholar: Look up in Google Scholar


Balogh, Bollobás and Weinreich showed that a parameter that has since been termed the distinguishing number can be used to identify a jump in the possible speeds of hereditary classes of graphs at the sequence of Bell numbers.

We prove that every hereditary class that lies above the Bell numbers and has finite distinguishing number contains a boundary class for well-quasi-ordering. This means that any such hereditary class which in addition is defined by finitely many minimal forbidden induced subgraphs must contain an infinite antichain. As all hereditary classes below the Bell numbers are well-quasi-ordered, our results complete the answer to the question of well-quasi-ordering for hereditary classes with finite distinguishing number.

We also show that the decision procedure of Atminas, Collins, Foniok and Lozin to decide the Bell number (and which now also decides well-quasi-ordering for classes of finite distinguishing number) has run time bounded by an explicit (quadruple exponential) function of the order of the largest minimal forbidden induced subgraph of the class.

Item Type: Journal Item
ISSN: 1097-0118
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 68077
Depositing User: Robert Brignall
Date Deposited: 12 Nov 2019 10:09
Last Modified: 13 Nov 2019 18:01
Share this page:

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU