pith. sign in

arxiv: 2410.02695 · v2 · submitted 2024-10-03 · 🧮 math.CO · cs.DM· math.PR

Fractional list packing for layered graphs

Stijn Cambie , Wouter Cames van Batenburg This is my paper

Pith reviewed 2026-05-23 20:03 UTC · model grok-4.3

classification 🧮 math.CO cs.DMmath.PR
keywords fractional list packinglist colouringpathwidthflexible colouringdegenerate graphsCartesian productscorrespondence colouring
0
0 comments X

The pith

The fractional list packing number of a graph is at most its pathwidth plus one.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the fractional list packing number χ_ℓ^•(G) as the smallest k such that some list assignment with lists of size k admits a probability distribution over proper list colorings where every color at each vertex appears with equal probability 1 over the list size. It establishes upper bounds on this number that strengthen for correspondence and local-degree variants, with a main result that the number is at most the pathwidth of G plus one. This yields improved theorems for flexible list colouring, including explicit bounds on Cartesian products and d-degenerate graphs. The pathwidth bound has no direct analogue when pathwidth is replaced by treewidth in the correspondence setting.

Core claim

χ_ℓ^•(G) ≤ pw(G) + 1 for every graph G, where pw denotes pathwidth, with the bound extending to correspondence and local-degree versions of the parameter; the corresponding statement with treewidth in place of pathwidth is false.

What carries the argument

A perfectly balanced probability distribution on proper L-colourings, meaning each colour appears with probability exactly 1/|L(v)| at every vertex v.

If this is right

  • Flexible list colouring theorems are strengthened for all Cartesian products and all d-degenerate graphs.
  • The same pathwidth-plus-one bound holds for the correspondence and local-degree strengthenings of the fractional list packing number.
  • No analogous bound exists when pathwidth is replaced by treewidth in the correspondence setting.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Path decompositions appear to be the structural feature that permits balancing colour probabilities across all vertices simultaneously.
  • The failure for treewidth suggests that the balancing condition is sensitive to the linear structure of path decompositions rather than to branchings.
  • It would be natural to test whether the bound remains tight on specific families such as grids or series-parallel graphs.

Load-bearing premise

The requirement that the probability distribution over colourings must be perfectly balanced, with each colour at a vertex having equal probability.

What would settle it

A single graph G with pathwidth w whose fractional list packing number exceeds w + 1, or a graph with treewidth w whose correspondence version of the fractional list packing number exceeds w + 1.

Figures

Figures reproduced from arXiv: 2410.02695 by Stijn Cambie, Wouter Cames van Batenburg.

Figure 1
Figure 1. Figure 1: Local extension of six correspondence-colouring [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A graph with pathwidth 3. Remark 5.6. A key feature of our strategy in Lemma 5.3 and its application in Theorem 5.4 is that we make the correspondence-colourings balanced “in only one direction”, based on the order in which the p-caterpillar is constructed. It is tempting to think that at the expense of increasing the list sizes we might ignore this order, thus enabling the construction of balanced colouri… view at source ↗
Figure 3
Figure 3. Figure 3: A 2-fold correspondence-cover pH, Lq of the hypercube Q3, demonstrating that χ ‚ c pQ3q ą 3. For each vertex v of Q3, its list Lpvq “ t1v, 2vu is indicated by a grey ellipse surrounding a white dot representing 1v and a black dot representing 2v. For most edges uv of Q3, the matching between Lpuq and Lpvq is the ‘identity matching’, consisting of edges 1u1v and 2u2v in H. The exceptions are formed by a mat… view at source ↗
Figure 4
Figure 4. Figure 4: A graph G with treewidth 3 and χ ‚ c pGq “ 5 [PITH_FULL_IMAGE:figures/full_fig_p020_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A correspondence-cover pL, Hq of the graph G in [PITH_FULL_IMAGE:figures/full_fig_p020_5.png] view at source ↗
read the original abstract

The fractional list packing number $\chi_{\ell}^{\bullet}(G)$ of a graph $G$ 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 $L:V(G)\rightarrow 2^{\mathbb{N}}$ need to be to ensure the existence of a `perfectly balanced' probability distribution on proper $L$-colourings, i.e., such that at every vertex $v$, every colour appears with equal probability $1/|L(v)|$. In this work we give various bounds on $\chi_{\ell}^{\bullet}(G)$, 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 $d$-degenerate graphs, and we prove that $\chi_{\ell}^{\bullet}(G)$ is bounded from above by the pathwidth of $G$ plus one. The correspondence analogue of the latter is false for treewidth instead of pathwidth.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 4 minor

Summary. The manuscript defines the fractional list packing number χ_ℓ^•(G) as the minimum k such that some k-list assignment L admits a probability distribution over proper L-colorings in which each color appears with equal probability 1/|L(v)| at every vertex v. It establishes upper bounds on this parameter for Cartesian products, d-degenerate graphs and layered graphs, proves that χ_ℓ^•(G) ≤ pw(G) + 1, and exhibits a counterexample showing that the analogous statement fails when pathwidth is replaced by treewidth in the correspondence-coloring setting. Corollaries improve known results on flexible list colouring.

Significance. If the stated bounds and the pathwidth theorem hold, the work supplies concrete structural upper bounds on a recently introduced invariant that refines ordinary list colouring, distinguishes pathwidth from treewidth in the correspondence model, and yields strengthened theorems on flexible colouring. The explicit use of perfectly balanced distributions is built into the definition and enables the pathwidth result; the counterexample for treewidth is a useful negative result.

minor comments (4)
  1. [§1] §1: the title emphasises layered graphs, yet the abstract and introduction state results for broader classes; add a sentence clarifying the role of layered graphs in the main theorems.
  2. [Definition 2.3] Definition 2.3: the notation χ_ℓ^•(G) is introduced without an immediate comparison table to χ_ℓ(G) and χ^•(G); a short comparison would aid readability.
  3. [Theorem 4.2] Theorem 4.2 (pathwidth bound): the proof sketch in the text is concise; expand the inductive step on the path decomposition to make the construction of the balanced distribution fully explicit.
  4. [Figure 3] Figure 3 (counterexample for treewidth): the caption does not state the exact list sizes or the correspondence edges used; add these parameters for reproducibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, recognition of its significance, and recommendation for minor revision. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; bounds derived from structural parameters

full rationale

The paper defines χ_ℓ^•(G) explicitly via the minimum k admitting a list assignment with perfectly balanced distributions on proper L-colorings. It then proves χ_ℓ^•(G) ≤ pw(G) + 1 (and related bounds for degenerate graphs and Cartesian products) using path decompositions and probabilistic arguments on the graph structure. These steps rely on the definition but do not reduce the claimed inequality to a tautology or fitted input by construction; the pathwidth bound is obtained from the layered structure rather than being presupposed. The explicit counterexample for treewidth in the correspondence setting further shows the result is not forced by the modeling choice. No self-citations, ansatzes, or renamings are load-bearing in the central derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based solely on the abstract, no explicit free parameters, ad-hoc axioms, or invented entities are identifiable; the work relies on standard definitions from graph theory and list coloring.

pith-pipeline@v0.9.0 · 5714 in / 1062 out tokens · 21236 ms · 2026-05-23T20:03:15.699696+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

  1. [1]

    M. O. Albertson. You can’t paint yourself into a corner. Journal of Combinatorial Theory, Series B, 73(2):189–194, 1998

    work page 1998

  2. [2]

    M. O. Albertson and E. H. Moore. Extending graph coloring s. J. Comb. Theory, Ser. B , 77(1):83– 95, 1999. 16

    work page 1999

  3. [3]

    Arnborg and A

    S. Arnborg and A. Proskurowski. Linear time algorithms f or NP-hard problems restricted to partial k-trees. Discrete Applied Mathematics , 23(1):11–24, 1989

    work page 1989

  4. [4]

    Baste, I

    J. Baste, I. Sau, and D. M. Thilikos. Hitting minors on boun ded treewidth graphs. IV. An optimal algorithm. SIAM J. Comput. , 52(4):865–912, 2023

    work page 2023

  5. [5]

    Bernshteyn

    A. Bernshteyn. The asymptotic behavior of the correspond ence chromatic number. Discrete Math., 339(11):2680–2692, 2016

    work page 2016

  6. [6]

    Bernshteyn and A

    A. Bernshteyn and A. Kostochka. On differences between DP- coloring and list coloring. Sib. Adv. Math. , 29:183–189, 2019

    work page 2019

  7. [7]

    Borowiecki, S

    M. Borowiecki, S. Jendrol’, D. Král’, and J. Miškuf. List c oloring of cartesian products of graphs. Discrete Mathematics , 306(16):1955–1958, 2006

    work page 1955

  8. [8]

    Bradshaw, T

    P. Bradshaw, T. Masařík, and L. Stacho. Flexible list colo rings in graphs with special degeneracy conditions. J. Graph Theory , 101(4):717–745, 2022

    work page 2022

  9. [9]

    Cambie, W

    S. Cambie, W. Cames van Batenburg, E. Davies, and R. J. Kang . List packing number of bounded degree graphs. arXiv e-prints (to appear in CPC) , Mar. 2023. arXiv:2303.01246

    work page arXiv 2023

  10. [10]

    Cambie, W

    S. Cambie, W. Cames van Batenburg, E. Davies, and R. J. Kan g. Packing list-colorings. Random Structures & Algorithms , 64(1):62–93, 2024

    work page 2024

  11. [11]

    Cambie, W

    S. Cambie, W. Cames van Batenburg, and X. Zhu. Disjoint li st-colorings for planar graphs. arXiv e-prints , 2023. arXiv:2312.17233

    work page arXiv 2023

  12. [12]

    Cambie and R

    S. Cambie and R. Hämäläinen. Packing colourings in comp lete bipartite graphs and the in- verse problem for correspondence packing. arXiv e-prints (to appear in JGT) , Mar. 2023. arXiv:2303.01944

    work page arXiv 2023

  13. [13]

    Camrud, E

    E. Camrud, E. Davies, A. Karduna, and H. Lee. Sampling li st packings. arXiv e-prints , 2024. arXiv:2402.03520

    work page arXiv 2024

  14. [14]

    Chakraborti and T

    D. Chakraborti and T. Tran. Approximate packing of inde pendent transversals in locally sparse graphs, 2024. arXiv:2402.02815

    work page arXiv 2024

  15. [15]

    Courcelle

    B. Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform. and Comput. , 85(1):12–75, 1990

    work page 1990

  16. [16]

    D. W. Cranston and E. Smith-Roberge. List-Coloring Pac king and Correspondence-Coloring Packing of Planar Graphs. arXiv e-prints , Jan. 2024. arXiv:2401.01332

    work page arXiv 2024

  17. [17]

    Dvořák and B

    Z. Dvořák and B. Lidický. Fine structure of 4-critical tr iangle-free graphs ii. planar triangle-free graphs with two precolored 4-cycles. SIAM Journal on Discrete Mathematics , 31(2):865–874, 2017

    work page 2017

  18. [18]

    Dvořák, S

    Z. Dvořák, S. Norin, and L. Postle. List coloring with re quests. J. Graph Theory , 92(3):191–206, 2019

    work page 2019

  19. [19]

    Edwards and A

    K. Edwards and A. G. J. van den Heuvel Ross J. Kang Gregory J. Puleo Jean-Sébastien Sereni. Extension from precoloured sets of edges. Electronic Journal of Combinatorics , 25(3):Paper 3.1, 2018. 17

    work page 2018

  20. [20]

    Erdős, A

    P. Erdős, A. L. Rubin, and H. Taylor. Choosability in gra phs. In Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (H umboldt State Univ., Arcata, Calif., 1979) , Congress. Numer., XXVI, pages 125–157. Utilitas Math., Wi nnipeg, Man., 1980

    work page 1979

  21. [21]

    M. R. Fellows, F. V. Fomin, D. Lokshtanov, F. Rosamond, S . Saurabh, S. Szeider, and C. Thomassen. On the complexity of some colorful problems pa rameterized by treewidth. Infor- mation and Computation , 209(2):143–153, 2011

    work page 2011

  22. [22]

    F. Galvin. The List Chromatic Index of a Bipartite Multig raph. Journal of Combinatorial Theory, Series B , 63(1):153–158, Jan. 1995

    work page 1995

  23. [23]

    H. Kaul, R. Mathew, J. A. Mudrock, and M. J. Pelsmajer. Fl exible list colorings: maximizing the number of requests satisfied. J. Graph Theory , 106(4):887–906, 2024

    work page 2024

  24. [24]

    Kaul and J

    H. Kaul and J. A. Mudrock. Counting packings of list-col orings of graphs. arXiv e-prints , 2024. arXiv:2401.11025

    work page arXiv 2024

  25. [25]

    H. Kaul, J. A. Mudrock, G. Sharma, and Q. Stratton. DP-co loring Cartesian products of graphs. J. Graph Theory , 103(2):285–306, 2023

    work page 2023

  26. [26]

    Molloy and L

    M. Molloy and L. Postle. Asymptotically good edge corre spondence colourings. Journal of Graph Theory, 100(3):559–577, 2022

    work page 2022

  27. [27]

    J. A. Mudrock. A short proof that the list packing number of any graph is well defined. Discrete Mathematics, 346(11):113185, 2023. Special issue in honour of Landon Ra bern

    work page 2023

  28. [28]

    S. D. Noble. Evaluating the Tutte polynomial for graphs of bounded tree-width. Combin. Probab. Comput., 7(3):307–321, 1998

    work page 1998

  29. [29]

    Proskurowski

    A. Proskurowski. Maximal graphs of path-width k or searching a partial k-cate rpillar. University of Oregon. Department of Computer and Information Science, 1989

    work page 1989

  30. [30]

    Rosenfeld

    M. Rosenfeld. Another approach to non-repetitive colo rings of graphs of bounded degree. Elec- tron. J. Comb. , 27(3):research paper p3.43, 16, 2020

    work page 2020

  31. [31]

    Sabidussi

    G. Sabidussi. Graphs with given group and given graph-t heoretical properties. Canadian Journal of Mathematics , 9:515–525, 1957

    work page 1957

  32. [32]

    Thomassen

    C. Thomassen. Every planar graph is 5-choosable. J. Combin. Theory Ser. B , 62(1):180–181, 1994

    work page 1994

  33. [33]

    Thomassen

    C. Thomassen. Exponentially many 5-list-colorings of planar graphs. J. Combin. Theory Ser. B , 97(4):571–583, 2007

    work page 2007

  34. [34]

    Thomassen

    C. Thomassen. The chromatic polynomial and list colori ngs. J. Comb. Theory, Ser. B , 99(2):474– 479, 2009

    work page 2009

  35. [35]

    Z. Tuza. Graph colorings with local constraints—a surv ey. Discuss. Math. Graph Theory , 17(2):161–228, 1997

    work page 1997

  36. [36]

    V. G. Vizing. Coloring the vertices of a graph in prescri bed colors. Diskret. Analiz, (29, Metody Diskret. Anal. v Teorii Kodov i Shem):3–10, 101, 1976

    work page 1976

  37. [37]

    R. Yuster. On factors of independent transversals in k-partite graphs. Electron. J. Combin. , 28(4):Paper No. 4.23, 18, 2021. 18 Appendix A The hypercube Q3 Figure 3: A 2-fold correspondence-cover pH, L q of the hypercube Q3, demonstrating that χ ‚ cpQ3q ą 3. For each vertex v of Q3, its list Lpvq “ t 1v, 2vu is indicated by a grey ellipse surrounding a w...

    work page 2021