pith. sign in

arxiv: 1907.01863 · v1 · pith:WKTXJPUUnew · submitted 2019-07-03 · 💻 cs.DM · math.CO

Linear transformations between colorings in chordal graphs

Nicolas Bousquet , Valentin Bartier This is my paper

Pith reviewed 2026-05-25 09:55 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords chordal graphscoloring reconfigurationdegenerate graphslinear transformationperfect elimination orderinglinear time algorithmgraph coloring
0
0 comments X

The pith

Chordal graphs admit linear-length transformations between any two k-colorings when k >= d+4.

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

The paper shows that chordal graphs allow any two proper k-colorings to be turned into each other by recoloring one vertex at a time while staying proper, and that the number of steps needed is at most some function of the maximum degree times the number of vertices, provided k is at least the degeneracy plus four. This improves on the exponential-length sequences known to exist for arbitrary d-degenerate graphs. The authors give an explicit construction that also runs in linear time. A sympathetic reader would see this as tightening the gap between the quadratic lower bounds that hold at k = d+2 and the linear upper bounds already known at k = 2d+2, but now available at a smaller number of colors thanks to the chordal structure.

Core claim

We prove that, as long as k >= d+4, there exists a transformation of length at most f(Delta) * n between any pair of k-colorings of chordal graphs. The proof is constructive and provides a linear time algorithm that, given two k-colorings c1 and c2, computes a linear transformation between c1 and c2.

What carries the argument

The perfect elimination ordering of a chordal graph, which permits inductive recoloring of simplicial vertices while preserving properness and bounding the total steps.

If this is right

  • The reconfiguration graph for k-colorings of chordal graphs has diameter O(f(Delta) n) when k >= d+4.
  • A linear-time procedure exists to output an explicit sequence of recolorings connecting any given pair.
  • The linear bound applies specifically because of chordal structure and does not hold for general d-degenerate graphs at this value of k.

Where Pith is reading between the lines

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

  • The same linear bound may hold for chordal graphs already at k = d+3, which the paper does not address.
  • The technique might extend directly to other elimination-order classes such as interval graphs.
  • Making the function f(Delta) explicit would allow concrete numerical bounds for applications.

Load-bearing premise

The chordal property is enough to guarantee that recoloring sequences can be kept linear in n rather than exponential when k is at least d plus four.

What would settle it

A chordal graph together with two k-colorings for k = d+4 whose shortest valid recoloring sequence has length superlinear in the number of vertices.

read the original abstract

Let $k$ and $d$ be such that $k \ge d+2$. Consider two $k$-colorings of a $d$-degenerate graph $G$. Can we transform one into the other by recoloring one vertex at each step while maintaining a proper coloring at any step? Cereceda et al. answered that question in the affirmative, and exhibited a recolouring sequence of exponential length. If $k=d+2$, we know that there exists graphs for which a quadratic number of recolorings is needed. And when $k=2d+2$, there always exists a linear transformation. In this paper, we prove that, as long as $k \ge d+4$, there exists a transformation of length at most $f(\Delta) \cdot n$ between any pair of $k$-colorings of chordal graphs (where $\Delta$ denotes the maximum degree of the graph). The proof is constructive and provides a linear time algorithm that, given two $k$-colorings $c_1,c_2$ computes a linear transformation between $c_1$ and $c_2$.

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 / 2 minor

Summary. The manuscript proves that for any chordal graph G with degeneracy d and maximum degree Δ, and for any k ≥ d+4, there exists a recoloring sequence of length at most f(Δ)·n transforming any k-coloring c1 into any other k-coloring c2. The proof is constructive, exploits perfect elimination orderings, and yields a linear-time algorithm that, given c1 and c2, outputs such a sequence.

Significance. If the claimed linear bound holds, the result improves the known exponential-length sequences for general d-degenerate graphs (Cereceda et al.) to linear length specifically for chordal graphs in the regime k ≥ d+4, while retaining a constructive linear-time algorithm. This strengthens the reconfiguration landscape by isolating the benefit of chordal structure (perfect elimination orderings) and supplies an explicit algorithmic procedure.

minor comments (2)
  1. [Abstract / §1] The dependence of the function f on Δ is stated only asymptotically in the abstract and introduction; an explicit expression or recurrence for f should be given in §3 or §4 so that the precise degree of the polynomial in Δ is visible.
  2. [§4] The linear-time claim for the algorithm is asserted but the running-time analysis is not broken down by the steps that use the perfect elimination ordering; a short paragraph or lemma bounding the total time by O(n + m) would strengthen the algorithmic contribution.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the supportive summary, significance assessment, and recommendation of minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central claim is a constructive proof that chordal graphs admit linear-length recoloring sequences for k >= d+4, using perfect elimination orderings to improve on the exponential bound for general d-degenerate graphs from external work (Cereceda et al.). No equations reduce by construction to inputs, no parameters are fitted then renamed as predictions, and the cited prior result is independent (not self-citation). The derivation is self-contained against the structural assumptions of chordal graphs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that chordal graphs admit perfect elimination orderings or equivalent structural decompositions that permit short recoloring paths; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Chordal graphs possess a perfect elimination ordering that can be used to control recoloring sequences.
    Invoked implicitly to obtain the linear bound instead of the exponential bound for general degenerate graphs.

pith-pipeline@v0.9.0 · 5728 in / 1373 out tokens · 46678 ms · 2026-05-25T09:55:35.417280+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

13 extracted references · 13 canonical work pages · 3 internal anchors

  1. [1]

    3 Marthe Bonamy and Nicolas Bousquet

    URL: http://dx.doi.org/10.1007/s10878-012-9490-y, doi:10.1007/s10878-012-9490-y. 3 Marthe Bonamy and Nicolas Bousquet. Token sliding on chordal graphs. InGraph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017 , pages 127–139,

    work page doi:10.1007/s10878-012-9490-y 2017

  2. [2]

    Shortest Reconfiguration of Matchings

    7 Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito, and Moritz Mühlenthaler. Shortest reconfiguration of matchings. CoRR, abs/1812.05419,

    work page internal anchor Pith review Pith/arXiv arXiv

  3. [3]

    A polynomial version of Cereceda's conjecture

    arXiv:1903.05619. 9 Nicolas Bousquet and Arnaud Mary. Reconfiguration of graphs with connectivity constraints. In Approximation and Online Algorithms - 16th International Workshop, W AOA 2018 , pages 295–309,

    work page internal anchor Pith review Pith/arXiv arXiv 1903

  4. [4]

    10 Nicolas Bousquet and Guillem Perarnau

    doi:10.1007/978-3-030-04693-4\_18. 10 Nicolas Bousquet and Guillem Perarnau. Fast recoloring of sparse graphs.Eur. J. Comb. , 52:1–11,

    work page doi:10.1007/978-3-030-04693-4

  5. [5]

    ESA 2019 11:26 Linear transformations between colorings in chordal graphs 13 L

    URL: http://dx.doi.org/10.1016/j.ejc.2009.03.011, doi:10.1016/j.ejc.2009.03.011. ESA 2019 11:26 Linear transformations between colorings in chordal graphs 13 L. Cereceda, J. van den Heuvel, and M. Johnson. Finding paths between 3-colorings.Journal of Graph Theory , 67(1):69–82,

    work page doi:10.1016/j.ejc.2009.03.011 2009

  6. [6]

    14 Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, and Luke Postle

    URL: http://dx.doi.org/10.1002/jgt.20514, doi: 10.1002/jgt.20514. 14 Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, and Luke Postle. Improved bounds for randomly sampling colorings via linear programming. InProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 , pages 2216–2234,

    work page doi:10.1002/jgt.20514 2019

  7. [7]

    doi:10.1137/1.9781611975482.134. 15 R. Diestel. Graph Theory, volume 173 ofGraduate Texts in Mathematics . Springer-Verlag, Heidelberg, third edition,

    work page doi:10.1137/1.9781611975482.134

  8. [8]

    Paths between colourings of graphs with bounded tree-width.Information Processing Letters, 144, 12 2018.doi:10.1016/j.ipl.2018.12.006

    17 Carl Feghali. Paths between colourings of graphs with bounded tree-width.Information Processing Letters, 144, 12 2018.doi:10.1016/j.ipl.2018.12.006. 18 Carl Feghali, Matthew Johnson, and Daniël Paulusma. A reconfigurations analogue of brooks’ theorem and its consequences.Journal of Graph Theory , 83(4):340–358,

    work page doi:10.1016/j.ipl.2018.12.006 2018

  9. [9]

    20 Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto

    Springer Berlin Heidelberg. 20 Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto. Reconfiguration of maximum-weight b-matchings in a graph. InComputing and Combinatorics - 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings, pages 287–296,

    work page 2017

  10. [10]

    21 Daniel Lokshtanov and Amer E. Mouawad. The complexity of independent set reconfiguration on bipartite graphs. InProceedings of the Symposium on Discrete Algorithms, SODA 2018 , pages 185–195,

    work page 2018

  11. [11]

    On the non-ergodicity of the Swendsen–Wang–Kotecký algorithm on the Kagomé lattice.Journal of Statistical Mechanics: Theory and Experiment , 2010(05):P05016,

    22 Bojan Mohar and Jesús Salas. On the non-ergodicity of the Swendsen–Wang–Kotecký algorithm on the Kagomé lattice.Journal of Statistical Mechanics: Theory and Experiment , 2010(05):P05016,

    work page 2010

  12. [13]

    URL: http://arxiv.org/abs/1401.5714. 25 J. van den Heuvel.The Complexity of change , page

    work page internal anchor Pith review Pith/arXiv arXiv

  13. [14]

    Part of London Mathematical Society Lecture Note Series. S. R. Blackburn, S. Gerke, and M. Wildon edition, 2013

    work page 2013