Countable Graphs with Finite Path-width: Characterisation and Universality

Abstract

We study path-width and the closely related parameter line-width in countably infinite graphs. Our first result characterises the graphs of finite path-width: they are the graphs that do not have infinitely many vertices of infinite degree, do not have infinitely many pairwise disjoint infinite paths, and contain no subdivision of some finite tree of maximum degree 3. We then investigate universality under the subgraph relation for graphs of bounded path-width or line-width. In particular, we prove that there exists a universal graph with line-width 𝒪(k²) for the class of graphs with line-width at most k. In contrast, we show that no graph of finite path-width is universal for the class of locally finite graphs with path-width $1$. Finally, we show that for each k≥ 2, every universal graph for the class of graphs with path-width at most k has line-width at least k + 1.

Translation Universality and Countable Configuration Theory for Dense Gδ-Sets in Polish Abelian Groups
Sidney A. Morris
Axioms4 Nov 2026Peer-reviewedCC BY 4.0General mathematicsCrossref
Typical properties of countable graphs: flows and bridges
Robert Šámal, Hadi Zamani
arXiv23 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Finite-index extensions of essentially free countable Borel equivalence relations
Jason Zesheng Chen
arXiv17 Sep 2026PreprintCC BY 4.0Full textLogic & foundationsarXiv
Edge universality of random regular graphs of growing degrees
Jiaoyang Huang, Horng‐Tzer Yau
The Annals of Probability28 Aug 2026Peer-reviewedLicence not statedFull text6 citedStatisticsOpenAlex
Power-of-two cycles in projective cubic graphs of large edge-width
Jean-François Culus
HAL15 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsHALarXiv

Cite

BibTeX RIS

BibTeX

@misc{huynh2026countable,
  title = {{Countable Graphs with Finite Path-width: Characterisation and Universality}},
  author = {Tony Huynh and Freddie Illingworth and Nikolai Karol and Florian Lehner and Chun-Hung Liu and János Pach and David R. Wood},
  howpublished = {arXiv},
  year = {2026},
  month = aug,
  doi = {10.48550/arxiv.2608.27752},
  eprint = {2608.27752},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.27752},
  note = {CC BY-NC-ND 4.0},
}

RIS

TY  - UNPB
TI  - Countable Graphs with Finite Path-width: Characterisation and Universality
AU  - Tony Huynh
AU  - Freddie Illingworth
AU  - Nikolai Karol
AU  - Florian Lehner
AU  - Chun-Hung Liu
AU  - János Pach
AU  - David R. Wood
PY  - 2026
DA  - 2026/08/27
PB  - arXiv
DO  - 10.48550/arxiv.2608.27752
UR  - https://arxiv.org/abs/2608.27752
AB  - We study path-width and the closely related parameter line-width in countably infinite graphs. Our first result characterises the graphs of finite path-width: they are the graphs that do not have infinitely many vertices of infinite degree, do not have infinitely many pairwise disjoint infinite paths, and contain no subdivision of some finite tree of maximum degree 3. We then investigate universality under the subgraph relation for graphs of bounded path-width or line-width. In particular, we prove that there exists a universal graph with line-width 𝒪(k^2) for the class of graphs with line-width at most k. In contrast, we show that no graph of finite path-width is universal for the class of locally finite graphs with path-width $1$. Finally, we show that for each k≥ 2, every universal graph for the class of graphs with path-width at most k has line-width at least k + 1.
ER  -

Abstract

Related

Cite