EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Fractional List Packing for Layered Graphs

Stijn Cambie, Wouter Cames van Batenburg

Journal of Graph Theory · 2026-09 · 113 (1) · 19-37

DOI: 10.1002/jgt.70048 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 19.04.2026. Verfasst von Stijn Cambie und 1 weiteren Autor:innen. Die Arbeit nennt 38 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The fractional list packing number of a graph is a graph invariant that has recently arisen from the study of disjoint list‐colourings. It measures how large the lists of a list‐assignment need to be to ensure the existence of a “perfectly balanced” probability distribution on proper ‐colourings, that is, such that at every vertex , every colour appears with equal probability . In this work we give various bounds on , which admit strengthenings for correspondence and local‐degree versions. As a corollary, we improve theorems on the related notion of flexible list colouring. In particular we study Cartesian products and ‐degenerate graphs, and we prove that is bounded from above by the pathwidth of plus one. The correspondence analogue of the latter is false for treewidth instead of pathwidth.

Zitieren

APA

Cambie, S., & Batenburg, W. C. V. (2026). Fractional List Packing for Layered Graphs. Journal of Graph Theory, 113(1), 19-37. https://doi.org/10.1002/jgt.70048

Vancouver

Cambie S, Batenburg WCV. Fractional List Packing for Layered Graphs. Journal of Graph Theory. 2026;113(1):19-37. doi:10.1002/jgt.70048

BibTeX
@article{Cambie2026,
  author = {Cambie, Stijn and Batenburg, Wouter Cames van},
  title = {Fractional List Packing for Layered Graphs},
  journal = {Journal of Graph Theory},
  year = {2026},
  volume = {113},
  number = {1},
  pages = {19--37},
  doi = {10.1002/jgt.70048}
}
Kostenlos starten →