The vertex sets of subtrees of a tree

Maria Chudnovsky; Tung Nguyen; Alex Scott; Paul Seymour

doi:10.37236/14646

The vertex sets of subtrees of a tree

Maria Chudnovsky
, Tung Nguyen
, Alex Scott
, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

Let F be a set of subsets of a set W . When is there a tree T with vertex set W such that each member of F is the set of vertices of a subtree of T ? It is necessary that F has the Helly property and the intersection graph of F is chordal. We will show that these two necessary conditions are together sufficient in the finite case, and more generally, they are sufficient if no element of W belongs to infinitely many infinite sets in F.

Original language	English (US)
Article number	P2.7
Journal	Electronic Journal of Combinatorics
Volume	33
Issue number	2
DOIs	https://doi.org/10.37236/14646
State	Published - 2026

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.37236/14646

Cite this

@article{cbc99c53f4fe462bb2b4afac609312d3,

title = "The vertex sets of subtrees of a tree",

abstract = "Let F be a set of subsets of a set W . When is there a tree T with vertex set W such that each member of F is the set of vertices of a subtree of T ? It is necessary that F has the Helly property and the intersection graph of F is chordal. We will show that these two necessary conditions are together sufficient in the finite case, and more generally, they are sufficient if no element of W belongs to infinitely many infinite sets in F.",

author = "Maria Chudnovsky and Tung Nguyen and Alex Scott and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} The authors.",

year = "2026",

doi = "10.37236/14646",

language = "English (US)",

volume = "33",

journal = "Electronic Journal of Combinatorics",

issn = "1097-1440",

publisher = "Australian National University",

number = "2",

}

TY - JOUR

T1 - The vertex sets of subtrees of a tree

AU - Chudnovsky, Maria

AU - Nguyen, Tung

AU - Scott, Alex

AU - Seymour, Paul

N1 - Publisher Copyright: © The authors.

PY - 2026

Y1 - 2026

N2 - Let F be a set of subsets of a set W . When is there a tree T with vertex set W such that each member of F is the set of vertices of a subtree of T ? It is necessary that F has the Helly property and the intersection graph of F is chordal. We will show that these two necessary conditions are together sufficient in the finite case, and more generally, they are sufficient if no element of W belongs to infinitely many infinite sets in F.

AB - Let F be a set of subsets of a set W . When is there a tree T with vertex set W such that each member of F is the set of vertices of a subtree of T ? It is necessary that F has the Helly property and the intersection graph of F is chordal. We will show that these two necessary conditions are together sufficient in the finite case, and more generally, they are sufficient if no element of W belongs to infinitely many infinite sets in F.

UR - https://www.scopus.com/pages/publications/105036296882

UR - https://www.scopus.com/pages/publications/105036296882#tab=citedBy

U2 - 10.37236/14646

DO - 10.37236/14646

M3 - Article

AN - SCOPUS:105036296882

SN - 1097-1440

VL - 33

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 2

M1 - P2.7

ER -

The vertex sets of subtrees of a tree

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this