The poset of graphs ordered by induced containment

Smith, JP ORCID logoORCID: https://orcid.org/0000-0002-4209-1604, 2019. The poset of graphs ordered by induced containment. Journal of Combinatorial Theory, Series A, 168, pp. 348-373. ISSN 0097-3165

[thumbnail of 1390742_a2007_Smith.pdf]
Preview
Text
1390742_a2007_Smith.pdf - Post-print

Download (415kB) | Preview

Abstract

We study the poset G of all unlabelled graphs with H ≤ G if H occurs as an induced subgraph in G. We present some general results on the Möbius function of intervals of G and some results for specific classes of graphs. This includes a case where the Möbius function is given by the Catalan numbers, which we prove using discrete Morse theory, and another case where it equals the Fibonacci numbers, therefore showing that the Möbius function is unbounded. A classification of the disconnected intervals of G is presented, which gives a large class of non-shellable intervals. We also present several conjectures on the structure of G.

Item Type: Journal article
Publication Title: Journal of Combinatorial Theory, Series A
Creators: Smith, J.P.
Publisher: Elsevier
Date: November 2019
Volume: 168
ISSN: 0097-3165
Identifiers:
Number
Type
10.1016/j.jcta.2019.06.009
DOI
S0097316519300858
Publisher Item Identifier
1390742
Other
Divisions: Schools > School of Science and Technology
Record created by: Linda Sullivan
Date Added: 20 Apr 2021 15:53
Last Modified: 14 Jan 2022 11:34
URI: https://irep.ntu.ac.uk/id/eprint/42724

Actions (login required)

Edit View Edit View

Statistics

Views

Views per month over past year

Downloads

Downloads per month over past year