{"id":"cd9f87c0-e401-46a6-a4a8-6ca4a59cd82d","arxiv_id":"2507.06730","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For Sierpiński products of complete graphs, paths, and stars, the paper determines or bounds the minimum and maximum packing chromatic number over all connecting functions, and gives a polynomial-time recognition algorithm for products of two trees.","lead":"The authors define the Sierpiński (upper) packing chromatic number, the best and worst packing coloring over all ways of connecting the factors in a Sierpiński product, and compute it when the factors are complete graphs, paths, or stars. They also provide a polynomial-time algorithm to decide whether a graph is a Sierpiński product of two trees.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.2's proposed coloring assigns the spine vertex's color c(vi) to the first vertex of every attached path, so adjacent vertices share a color; Theorem 4.4's upper bound bχρ(P_m,P_n)≤7 therefore has no valid proof as written.","rationale":"The reader's REJECT verdict is justified. The abstract's headline claims for path products and complete products both rest on invalid upper-bound arguments. Lemma 4.2 is not a minor typo: the formula itself places the same color on adjacent vertices, so the asserted packing coloring is objectively not a packing coloring. Since Lemma 4.3 shows every Pm⊗f Pn belongs to the class T, the upper-bound side of Theorem 4.4 collapses once Lemma 4.2 is removed. The separate Theorem 3.5 gap, where Lemma 3.2 is applied outside its hypothesis n−1≥m, further confirms that the complete-graph exact-values section is not proven as written. The recognition algorithm in Section 5 is a different line of work and may survive, but it is not the paper's main contribution. No adjustment to the reader's rejection is needed.","tokens_in":14999,"tokens_out":11127,"duration_ms":117862,"concrete_test":"Build T=P_2 with one pendant leaf attached to v_1, which is a member of the class T. Apply the Lemma 4.2 coloring: the spine receives colors (1,4), and the attached leaf receives the first entry of the pattern c(v_1),2,1,3,..., namely 1. The leaf is adjacent to v_1, so color 1 appears at distance 1, violating the packing condition for color 1. This single instance refutes the lemma. To make the impact concrete, also apply the same recipe to Pm⊗gP3 for m=12 with the function g from Theorem 4.4 and verify that the resulting color classes are not packings.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Lemma 4.2, for each attached path Qi at spine vertex vi, the coloring is prescribed as c(vi), 2, 1, 3, 1, 2, 1, 3, ... . Thus the first vertex of Qi receives c(vi), and it is adjacent to vi, which also has color c(vi). This is a violation for every color: for color 1 the required separation is d>1, for colors ≥2 it is d>c(vi), and in all cases d=1. Consequently, the claim that 'it is now straightforward to check that c is a packing coloring' is false. Lemma 4.3 proves Pm⊗f Pn ∈ T, so the only supplied upper bound for bχρ(P_m,P_n) in Theorem 4.4 is the defective Lemma 4.2. The lower bound bχρ(P_m,P_n)≥6 via Pm⊙2K1 appears sound, but the equality-range claim {6,7} is not established. A separate gap occurs in Theorem 3.5: for non-surjective f with m≥n, the proof imports Lemma 3.2's conclusion of a size-m 2-packing into G'=Km⊗_{f'}K_{n-1}, although Lemma 3.2 requires n−1≥m; for K4⊗_fK3 with f=(1,1,2,2), the claimed disjoint independent and 2-packing pair of size 4 does not exist. I do not assert that the numerical statements are false; I assert that the submitted derivations fail at these points.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the Sierpiński packing chromatic number chi_rho(G,H) and the upper Sierpiński packing chromatic number bchi_rho(G,H), defined as the minimum and maximum of chi_rho(G ⊗_f H) over all connecting functions f. It claims exact values for complete graph factors: chi_rho(K_m,K_n)=mn-2m+2 for m,n≥3, and bchi_rho(K_m,K_n)=mn-2m+2 for n≥m and mn-m-n+2 for m≥n. It further claims that all four Sierpiński products of paths and stars have Sierpiński packing chromatic number 3, with upper bounds on the upper Sierpiński packing chromatic number, in particular bchi_rho(P_m,P_n)∈{6,7} for n≥3, m≥12. Finally, it gives a polynomial-time recognition algorithm for graphs that are Sierpiński products of two trees.","tokens_in":15337,"tokens_out":40416,"duration_ms":431206,"significance":"If the results were established, the complete graph formulas and the path/star bounds would be a useful contribution to the packing coloring literature, and the recognition algorithm would be a novel algorithmic contribution. The paper has several strengths: the definitions are clear, the lower bounds via corona theorems are sound in isolation, and the recognition algorithm in Section 5 is plausible and appears to be the most robust part of the manuscript. However, the submitted proofs contain load-bearing gaps, and at least one stated value in the complete graph section is false. The central claims for m,n≥3 may be salvageable, but the present derivations do not support them.","major_comments":[{"comment":"The coloring defined in Lemma 4.2 is not a packing coloring. For each attached path Q_i, the first vertex of Q_i receives the same color c(v_i) as the spine vertex v_i to which it is adjacent. Thus two vertices of the same color are at distance 1, which violates the packing condition d>ell for every color ell≥1. Since Lemma 4.3 shows that P_m ⊗_f P_n belongs to the class T, the upper bound bchi_rho(P_m,P_n)≤7 in Theorem 4.4 relies entirely on this defective lemma. The lower bound bchi_rho(P_m,P_n)≥6 via P_m ⊙ 2K_1 appears sound, but the claim {6,7} is not established as written.","section":"Lemma 4.2 and Theorem 4.4"},{"comment":"In the non-surjective case of Theorem 3.5, the proof asserts, by reference to Case 1 of Lemma 3.3, that G contains a disjoint 2-packing and an independent set both of size m. This inference is invalid. The referenced argument invokes Lemma 3.2, which requires the order of the second factor to be at least the order of the first; after deleting the unused fiber vertex, the second factor has order n-1 < m when m≥n. The claim is in fact false for K_4 ⊗_f K_3 with f=(1,1,2,2): the only 2-packing of size 4 is {(u_i,3): i∈[4]}, but there is no independent set of size 4 in the remaining graph disjoint from it. A direct check shows that selecting (u_1,1) forces (u_2,2) and then both (u_3,2) and (u_4,2), which are adjacent, while selecting (u_1,2) forces (u_3,2) and (u_4,2), which are adjacent. This case is needed for the upper bound in Theorem 3.5, so the theorem is not proved as written.","section":"Theorem 3.5, non-surjective f"},{"comment":"Lemma 3.3 also misapplies Lemma 3.2 when n=m and f is non-surjective, since after removing the unused vertex the second factor has order n-1 < m. Moreover, the proof as written does not assign a color to the set M={(u_i,n)} and then colors all remaining uncolored vertices with distinct colors, which would use more than mn-2m+2 colors. The intended argument presumably colors M with color 2, but even with that repair, the existence of an independent set of size m in G' requires a new proof that is not supplied.","section":"Lemma 3.3, Case 1"},{"comment":"The paragraph after Theorem 3.5 states that for m=2 the graph K_m ⊗_f K_n is 'a diameter 2 graph with α(G)=2, hence χ_ρ(G)=2n−1'. This is false for n≥3. The graph is two disjoint K_n cliques joined by a single edge and has diameter 3. For n=3, χ_ρ(K_2,K_3)=4: color one non-connecting vertex from each clique with 1, the other two non-connecting vertices with 2, and the two connecting vertices with 3 and 4. A 3-coloring is impossible because colors 1 and 2 can be used on at most two vertices each and color 3 can be used at most once, covering at most 5 of the 6 vertices. Consequently the claimed determination of the complete graph case for all m,n is not correct as stated. The same subsection's Proposition 3.6 also gives bchi_rho(K_3,K_2)=3, whereas the preceding case analysis (1) yields 4 for m=3.","section":"Section 3, case m=2"}],"minor_comments":[{"comment":"In the constant-function case of Lemma 3.1, the proof chooses vertices (u_j,i') and (u_l,i'') with i'≠i''; when n=2 no two distinct values different from the constant value exist. Choosing i'=i'' (the unique value different from the constant value) still gives distance 3, so the proof can be repaired.","section":"Lemma 3.1"},{"comment":"In the proof of Theorem 4.1, the notation V(K_m) appears where V(P_m) is intended; the base graph in that theorem is a path.","section":"Theorem 4.1"},{"comment":"The expression T ⊗_f |_{T-x} H is not defined; it should be something like (T-x) ⊗_{f|_{V(T-x)}} H.","section":"Lemma 5.1"},{"comment":"The 64-term coloring pattern on the shortest path Q is said to be 'found and verified by a computer', but no certificate or reproducible verification is provided; the proof should include a human-checkable certificate or the code used.","section":"Theorem 4.6"}],"recommendation":"major_revision","confidential_remarks":"The recognition algorithm in Section 5 is likely the strongest part and may survive intact. However, the complete graph section contains a false value (χ_ρ(K_2,K_3)=5 is claimed but the correct value is 4), and the proofs of Lemma 4.2, Lemma 3.3, and Theorem 3.5 have load-bearing gaps. I recommend major revision rather than outright rejection because the main formulas for m,n≥3 may be salvageable, but the authors will need to supply genuinely new arguments for Theorem 3.5 and Lemma 4.2, and to correct the corner cases in Section 3."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThis paper defines the Sierpiński packing chromatic number and its upper variant, then studies them for complete graphs, paths, stars, and gives a recognition algorithm for products with two tree factors. There is real content here: the definition is natural, and the complete-graph lower bound (Lemma 3.3) is a clean argument—diameter 3 plus α, α2 ≤ m forces many private colors. The recognition algorithm (Theorem 5.2) also looks plausible and is the kind of concrete result that warrants attention.\n\nThe soft spots are in two of the headline upper bounds. Lemma 4.2, which is the entire support for bχρ(P_m,P_n) ≤ 7, describes a coloring where the first vertex of every attached path gets the spine vertex's color c(v_i). That vertex is adjacent to v_i, so the same color appears at distance 1, violating the packing condition. The claim that it is straightforward to check is simply false. The lower bound via P_m ⊙ 2K_1 is fine, but without a valid upper bound the equality bχρ(P_m,P_n) ∈ {6,7} is unproven. Theorem 3.5 also has a gap: in the non-surjective case with m ≥ n, the proof imports Lemma 3.2's size-m 2-packing, which requires n−1 ≥ m; the concrete example K_4 ⊗_f K_3 with f=(1,1,2,2) shows the asserted disjoint independent set and 2-packing of size 4 do not exist. There is also a notational slip in Lemma 3.1's proof where u_j is used for values j > m.\n\nI want to be clear about the proportions: the complete-graph equalities for n ≥ m and the surjective m = n case look right, and the overall framework is sensible. The failures are in the upper-bound constructions, not in the basic definitions or the polynomial-time algorithm. The paper is not incoherent; it is a promising draft with a couple of load-bearing errors that would need to be repaired before the results can be trusted.\n\nI would send it to a referee rather than desk-reject, because the novel definition and the positive results deserve scrutiny. But the referee should be told to focus on Lemma 4.2 and Theorem 3.5. If those get fixed, this could be a solid contribution.","headline":"Novel setup and a solid recognition algorithm, but the path upper-bound proof has a load-bearing error and Theorem 3.5 has a gap; the paper needs major revision, not desk rejection.","tokens_in":15888,"tokens_out":3302,"would_cite":false,"duration_ms":32281,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C76","05C15","05C12","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper determines the Sierpiński packing chromatic number exactly for products of complete graphs, shows path and star products always pack with three colors, and gives a polynomial-time recognition test for tree products.","keywords":["Sierpiński product","packing chromatic number","upper Sierpiński packing chromatic number","complete graphs","paths and stars","tree recognition","corona graphs","packing coloring"],"falsifier":"Take the tree consisting of a two-vertex spine with one pendant path of length 2 attached to one spine vertex and apply the Lemma 4.2 pattern: the spine vertex receives color 1 and the first path vertex also receives color 1, so two adjacent vertices lie in the same color class, which is not a packing coloring. Checking this single small tree falsifies the lemma as stated and thereby removes the current proof of the upper bound $b\\chi_\\rho(P_m,P_n)\\le 7$.","tokens_in":14785,"feed_emoji":"🎨","tokens_out":14687,"duration_ms":148132,"temperature":0.7,"pith_summary":"The paper defines the Sierpiński packing chromatic number $\\chi_\\rho(G,H)$ as the minimum, over all linking functions $f\\colon V(G)\\to V(H)$, of the packing chromatic number of the Sierpiński product $G\\otimes_f H$, and the upper Sierpiński packing chromatic number $b\\chi_\\rho(G,H)$ as the corresponding maximum. Its central result is exact: for $m,n\\ge 3$, $\\chi_\\rho(K_m,K_n)=mn-2m+2$, while $b\\chi_\\rho(K_m,K_n)$ equals $mn-2m+2$ when $n\\ge m$ and $mn-m-n+2$ when $m\\ge n$. The paper also proves that Sierpiński products of two paths or of a path and a star always have packing chromatic number $3$, bounds the worst case for those products by small constants ($6$ or $7$ for two paths under mild length conditions), and gives a polynomial-time algorithm to recognize graphs that are Sierpiński products of two trees. A careful reader cares because computing the packing chromatic number is hard even for trees, so exact best- and worst-case values over an entire product family are rare and concrete.","feed_headline":"Exact packing chromatic number found for clique Sierpiński products","feed_subtitle":"The paper fixes both the best and worst ways to glue two graphs, and adds a fast check for products built from trees.","key_machinery":"The central object is the Sierpiński product $G\\otimes_f H$: its vertex set is $V(G)\\times V(H)$, it contains a disjoint copy of $H$ over each vertex of $G$ (type-1 edges), and for each edge $gg'$ of $G$ it has one connecting edge $(g,f(g'))(g',f(g))$ (type-2 edges). The argument's engine is a packing coloring, in which every pair of vertices sharing color $i$ must be at distance greater than $i$, so each color class is an $i$-packing. For complete factors the proof uses three structural facts: the product has diameter $3$; every fiber is a clique, so no color can appear more than $m$ times; and the extremal colorings are built from one independent set and one $2$-packing of size $m$, with all other vertices left to private colors. For path and star factors the lower bounds are obtained by embedding corona graphs $P_n\\odot 2K_1$ and $P_n\\odot 3K_1$ as induced subgraphs, where the needed packing chromatic numbers are already known. The recognition algorithm rests on Lemma 5.1, which characterizes a pendant connecting edge as exactly a cut edge whose removal leaves components of orders $n(T)$ and $n(T\\otimes_f H)-n(T)$; this lets the algorithm peel fiber copies and test tree isomorphism at each step.","core_discovery":"For a fixed pair $G,H$, every choice of $f$ gives a different graph $G\\otimes_f H$, so the paper studies the range of the packing chromatic number across that family. The main discovery is that for complete factors the range is fully determined by the two parameters $m=|V(K_m)|$ and $n=|V(K_n)|$: the lower bound $mn-2m+2$ comes from the fact that each fiber is a clique (so at most $m$ vertices can share any color), the whole product has diameter $3$ (so colors larger than $2$ cannot be reused at all), and the bound is attained by a coloring that reserves one color class of size $m$ and one 2-packing of size $m$, then gives every remaining vertex a private color. The upper Sierpiński value is the same when the fiber is at least as large as the base, and is $mn-m-n+2$ when the base is larger, attained by a function that maps $n$ base vertices onto distinct fiber vertices and the remaining base vertices onto one fixed vertex. For paths and stars the paper shows that the minimum is always $3$ across all four factor combinations, while the maximum is bounded by $7$ for path–path and star–path products and by $9$ for path–star products, with sharper interval statements in several ranges. The recognition result is stated as Theorem 5.2: a connected graph can be tested in polynomial time for being isomorphic to $T_1\\otimes_f T_2$ for trees $T_1,T_2$, by using pendant connecting cut edges to peel off fiber copies one at a time.","pith_inferences":["Beyond the paper: if the same two invariants—independence number and 2-packing number—are determined for other factor pairs, the complete-graph proof pattern suggests closed formulas for their Sierpiński packing chromatic numbers may follow directly.","Beyond the paper: the peeling-by-cut-edges recognition strategy suggests a testable extension to factors that are not trees, for example any base graph with a known pendant-edge decomposition, where component orders after cut-edge removal would still identify fibers.","Beyond the paper: the three-colour results for stars and paths indicate that sparse factor pairs with small diameter-2 neighborhoods may always admit a three-colour linking function; testing complete bipartite factors would be a natural next step."],"forward_implications":["For $m,n\\ge 3$, the Sierpiński packing chromatic number of complete pairs is exactly $mn-2m+2$; every linking function uses at least that many colors and one linking function achieves it.","For $m\\ge 12$, $n\\ge 3$, every Sierpiński product of $P_m$ and $P_n$ can be packed with at most 7 colors and at least one product needs 6, so the upper Sierpiński value is 6 or 7.","For the four path/star combinations, the Sierpiński packing chromatic number is exactly 3, so the best linking function never needs more than three colors; the worst case stays within 7 or 9.","The recognition theorem gives a polynomial-time test for whether a given connected graph is a Sierpiński product of two trees, using the cut-edge structure of pendant connecting edges."],"supporting_citations":[{"why":"Supplies the packing chromatic numbers of the corona graphs P_n ⊙ 2K_1 and P_n ⊙ 3K_1 (Theorems 7–9), which generate the lower bounds 6 and 7 for path- and star-factor products.","marker":"[23]"},{"why":"Introduces the Sierpiński product graph and its basic properties; every structural argument and definition in this paper builds on this operation.","marker":"[22]"},{"why":"Defines the packing chromatic number and the i-packing condition underlying all of the paper's coloring arguments.","marker":"[12]"}],"fun_headline_variants":["Exact packing chromatic numbers for clique Sierpiński products","Sierpiński product coloring: extremes fixed for complete graphs","Complete Sierpiński products: packing chromatic number solved","Polynomial-time recognition of Sierpiński tree products","Packing chromatic range for Sierpiński products of cliques"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premises are that the Lemma 4.2 coloring pattern on the tree class is a legal packing coloring (the pattern assigns the first vertex of each attached path the same color as the adjacent spine vertex, placing two distance-1 vertices in one color class), and that in the $m\\ge n$ case of Theorem 3.5 the product $K_m\\otimes_f K_n$ contains disjoint independent and 2-packing sets of size $m$ for non-surjective $f$; the proof of the latter does not supply the required construction.","fun_headline_variants_meta":{"raw":{"variants":["Exact packing chromatic numbers for clique Sierpiński products","Sierpiński product coloring: extremes fixed for complete graphs","Complete Sierpiński products: packing chromatic number solved","Polynomial-time recognition of Sierpiński tree products","Packing chromatic range for Sierpiński products of cliques"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000991,"raw_usage":{"total_tokens":4332,"prompt_tokens":1209,"completion_tokens":3123,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":825,"completion_tokens_details":{"reasoning_tokens":3038}},"tokens_in":825,"tokens_out":3123,"duration_ms":27053,"temperature":1.0,"reasoning_tokens":3038,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:04:36.878593+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the tree consisting of a two-vertex spine with one pendant path of length 2 attached to one spine vertex and apply the Lemma 4.2 pattern: the spine vertex receives color 1 and the first path vertex also receives color 1, so two adjacent vertices lie in the same color class, which is not a packing coloring. Checking this single small tree falsifies the lemma as stated and thereby removes the current proof of the upper bound $b\\chi_\\rho(P_m,P_n)\\le 7$.","supporting_citations":[{"cited_title":"La ¨ ıche, I","cited_arxiv_id":null,"evidence_quote":"Supplies the packing chromatic numbers of the corona graphs P_n ⊙ 2K_1 and P_n ⊙ 3K_1 (Theorems 7–9), which generate the lower bounds 6 and 7 for path- and star-factor products."},{"cited_title":"Koviˇ c, T","cited_arxiv_id":null,"evidence_quote":"Introduces the Sierpiński product graph and its basic properties; every structural argument and definition in this paper builds on this operation."}],"review_version":1}