Extending partial edge-colorings of bounded size in Cartesian products of graphs

Ervin Gy\H{o}ri; P\'al B\"arnkopf

arxiv: 2603.23139 · v2 · submitted 2026-03-24 · 🧮 math.CO

Extending partial edge-colorings of bounded size in Cartesian products of graphs

P\'al B\"arnkopf , Ervin Gy\H{o}ri This is my paper

Pith reviewed 2026-05-15 00:52 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C15

keywords edge-coloringCartesian productprecoloring extensiongraph productstriangle-free graphsregular graphschromatic index

0 comments

The pith

In Cartesian products G □ H, a partial edge-precoloring of size k + l + 1 extends to a proper χ'(G) + χ'(H) coloring when G is triangle-free regular and H is a tree or similar.

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

The paper studies the extension of partial edge-colorings on Cartesian products of graphs. It states a general hypothesis: if precolorings of size less than the chromatic index on each factor graph separately can always be extended, then a precoloring on the product using one extra color can be extended to a full proper coloring with the sum of the indices. The authors prove this hypothesis holds in several concrete cases, including when the first graph is triangle-free and regular with the precoloring size below its maximum degree, and the second graph is a star, even cycle, path, or any tree. They also prove the full statement when the first graph is subcubic and the second is a single edge.

Core claim

If every edge-precoloring of G of size k < χ'(G) extends to a proper χ'(G)-edge-coloring and every edge-precoloring of H of size l < χ'(H) extends to a proper χ'(H)-edge-coloring, then every edge-precoloring of the Cartesian product G □ H of size k + l + 1 extends to a proper (χ'(G) + χ'(H))-edge-coloring. The paper establishes this when k < Δ(G), G is triangle-free r-regular, and H is a star, even cycle, path, or arbitrary tree F; it also establishes the statement when G is subcubic and H = K₂.

What carries the argument

The Cartesian product G □ H, whose edge set is the disjoint union of copies of the edges of G and of H, so that a precoloring on the product decomposes into colorings on the factor graphs that can be extended independently.

If this is right

The stated hypothesis holds for every subcubic graph G paired with H = K₂.
The hypothesis holds for every triangle-free r-regular graph G paired with any tree H.
The hypothesis holds when H is an even cycle or a star and G satisfies the triangle-free regular condition with k below Δ(G).
Any precoloring of the product using at most one more color than the separate bounds on the factors becomes completable under the listed structural restrictions.

Where Pith is reading between the lines

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

The same extension technique might apply when H is bipartite, since the listed cases are all bipartite or cycle-based.
These special cases suggest that the general hypothesis could be proved by induction on the structure of H when H has bounded treewidth.
The results imply that certain grid-like or layered scheduling problems modeled by Cartesian products admit bounded precoloring extensions.

Load-bearing premise

The proofs require G to be triangle-free and regular (or subcubic) while H belongs to the restricted families of stars, even cycles, paths, trees, or single edges.

What would settle it

A counterexample consisting of a triangle-free regular graph G, a tree H, and a specific partial edge-coloring of G □ H that uses exactly Δ(G) + χ'(H) colors yet cannot be completed to a proper coloring, even though all smaller precolorings on G and on H separately do extend.

read the original abstract

This paper studies edge-precoloring extensions in Cartesian products of graphs, motivated by a conjecture of Casselgren, Petros, and Fufa. We formulate a general hypothesis stating that if every edge-precoloring of $G$ and $H$ of sizes $k<\chi'(G)$ and $l<\chi'(H)$, respectively, is extendable, then any edge-precoloring of $G \square H$ of size $k+l+1$ can be extended to a proper $(\chi'(G)+\chi'(H))$-coloring. We provide partial progress toward this conjecture by establishing the result in cases where $k<\Delta(G)$, $G$ is a triangle-free $r$-regular graph and $H$ is a star, an even cycle, a path or, more generally, an arbitrary tree $F$. Furthermore, we prove the conjecture in the case where $G$ is a subcubic graph and $H = K_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.

Desk Editor's Note private letter to a colleague

The paper verifies the extension conjecture for triangle-free regular graphs with trees and subcubic graphs with K2, adding clean new cases without overclaiming.

read the letter

The main takeaway is that this work confirms the edge-precoloring extension property for Cartesian products in two previously unhandled families. When G is triangle-free and r-regular with precoloring size k below the maximum degree, and H is any tree, the result holds. It also holds when G is subcubic and H is simply K2. These are explicit additions to the literature on the Casselgren-Petros-Fufa conjecture, stated with clear bounds on the precoloring sizes relative to the chromatic indices of the factors. The general hypothesis is formulated neatly at the start, and the authors restrict their claims to the cases they actually prove, which keeps the contribution proportionate. The structure of Cartesian products lends itself to layer-by-layer coloring arguments, and the choice to handle trees and the K2 case first makes sense as a stepping stone. The soft spots are limited. The abstract gives no proof sketches, so the depth of the case analysis for arbitrary trees or the subcubic matching arguments cannot be checked here, though the stress-test finds no internal contradictions or hidden assumptions. The general conjecture remains untouched, and the triangle-free or subcubic restrictions may be essential to the current methods. This is the kind of targeted combinatorial result that specialists in graph coloring and product graphs will want to see. A reader following Vizing-type problems or applications in network scheduling gets direct value from the new theorems. It deserves peer review because the statements are precise and the new cases are falsifiable additions to the record.

Referee Report

0 major / 2 minor

Summary. The manuscript formulates a general hypothesis on extending bounded-size partial edge-colorings of G and H to proper edge-colorings of the Cartesian product G □ H, and proves the hypothesis in two families of cases: (i) G triangle-free r-regular with k < Δ(G) and H a star, even cycle, path or arbitrary tree F; (ii) G subcubic and H = K₂.

Significance. The results constitute concrete partial progress on the Casselgren–Petros–Fufa conjecture. The proofs cover natural, frequently studied classes (triangle-free regular graphs, trees, subcubic graphs) and rest on standard graph-theoretic assumptions rather than circular or fitted constructions.

minor comments (2)

[Abstract] Abstract: the general hypothesis is stated only informally; a one-sentence formal version (with the precise bound k+l+1 and the target chromatic index χ'(G)+χ'(H)) would make the scope of the claimed theorems immediately clear.
[Section 1] Theorems 1.1–1.3 and 2.1: the statements list the structural hypotheses on G and H but do not explicitly record the extendability assumptions on the individual factors that appear in the general hypothesis; adding a short clause would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our manuscript, accurate summary of the results, and recommendation for minor revision. We appreciate the recognition of the partial progress toward the Casselgren–Petros–Fufa conjecture on natural graph classes.

Circularity Check

0 steps flagged

No circularity: proofs are self-contained case analysis on delimited graph classes

full rationale

The paper formulates a general hypothesis on precoloring extension in G □ H and then proves it only for explicitly restricted cases (G triangle-free r-regular with k < Δ(G) and H a star/even cycle/path/tree; or G subcubic and H = K2). These restrictions are stated openly; the arguments use standard Vizing-type edge-coloring lemmas, path augmentations, and case distinctions on the structure of H. No equation equates a claimed extension to a fitted parameter or to a self-referential definition. The motivating conjecture is attributed to external authors (Casselgren et al.). No load-bearing step reduces to a prior self-citation whose validity is assumed without independent verification. The derivation chain therefore consists of ordinary mathematical case analysis whose correctness can be checked directly against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard graph theory definitions with no free parameters, invented entities, or ad-hoc axioms visible in the abstract.

axioms (1)

standard math Basic properties of Cartesian products, proper edge-colorings, and chromatic index as defined in standard graph theory
Invoked throughout the statement of the hypothesis and the cases.

pith-pipeline@v0.9.0 · 5474 in / 1260 out tokens · 48892 ms · 2026-05-15T00:52:00.697259+00:00 · methodology

Extending partial edge-colorings of bounded size in Cartesian products of graphs

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)