{"id":"b76a4465-b07b-4a87-a0dd-2942388c87a8","arxiv_id":"2512.15486","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A split graph has k completely independent spanning trees roughly when its associated hypergraph admits a bipanchromatic k-coloring; deciding the case k=2 is NP-complete.","lead":"This paper links completely independent spanning trees in split graphs to new hypergraph-coloring notions, and proves that deciding whether such trees exist is NP-complete. A generalist might read it because it offers a compact hypergraph certificate for a network-fault-tolerance question.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5's proof that any bipanchromatic k-coloring of H(G) yields k CIST in G rests on an unproven application of Pai et al. [16], which only provides two internal vertices per tree, not arbitrary color classes; both the lower bound of Theorem 8 and the yes-direction of the NP-hardness reduction r","rationale":"The reader's weakest assumption is exactly the unsubstantiated use of Pai et al. in Theorem 5. I agree that this is the most load-bearing concern because Theorem 5 underpins both the lower bound of Theorem 8 and the yes-direction of the NP-completeness reduction (Theorem 10). The paper's proof does not justify that an arbitrary bipanchromatic coloring (with color classes of size ≥2) can be realized as internal vertex sets of CIST in the clique; the cited result only gives exactly two internal vertices per tree. Moreover, the extension to the independent set I is hand-waved. However, the issue is a proof gap rather than a falsehood: the partition conditions of Araki's theorem appear to hold for a clique with parts of size ≥2, and panchromaticity provides the needed leaf attachments. Thus the central claims are plausible, but the manuscript as written is not fully rigorous. The appropriate verdict remains CONDITIONAL, requiring a rewritten proof of Theorem 5 and a careful verification of the partition extension and of Theorem 7's Case 2. No change from the reader's CONDITIONAL verdict is needed.","tokens_in":11366,"tokens_out":26401,"duration_ms":251639,"concrete_test":"Independently verify Theorem 5 for a small hypergraph with a bipanchromatic 3-coloring where one color class has size 3 (e.g., D = {a,b,c,d,e}, color classes {a,b,c}, {d,e}, and hyperedges {a,d,x}, {b,e,y} appropriately extended). Construct the split graph G, then attempt to build 3 CIST using the partition V_1={a,b,c}, V_2={d,e}, V_3=... as a CIST-partition: check G[V_i] is connected and B(V_i,V_j) has no tree component in D, then attach each I vertex as a leaf to a distinct V_i neighbor. If the construction succeeds for all such cases (or if a direct verification shows the partition is always a CIST-partition), the gap is merely a missing proof; if a counterexample appears, Theorem 5 is false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Theorem 5, the authors assign each color class V_i as the internal-vertex set of tree T_i built in the clique D, justifying the construction with: 'From the result of Pai et al. [16], only two vertices in Kn suffice to construct each tree for each n>=4.' This does not establish the needed claim: a bipanchromatic coloring only guarantees each color appears at least twice; a color class may have size >2, and if we discard surplus vertices as leaves, a hyperedge could lose that color entirely (the hyperedge might contain only the discarded vertex of that color). Thus every vertex of a color class may need to be internal in the corresponding tree. The cited result gives trees with exactly two internal vertices, not trees whose internal set is an arbitrary prescribed set of size ≥2. The subsequent extension to I is also asserted without proof: 'each vertex of I is assigned arbitrarily to one of the previous sets' is claimed to preserve the CIST-partition conditions, but this requires checking that no tree component appears in B(V'_i, V'_j,G); the paper's one-sentence justification is not rigorous. Because Theorem 5 is used both for the lower bound χ2p ≤ M and for the yes-direction of the NP-completeness reduction (Theorem 10), this gap is load-bearing. That said, the claim is likely repairable: by Araki's Theorem 2, any partition of the clique D into parts of size at least 2 is a k-CIST-partition of D, and panchromaticity supplies each I vertex with a neighbor in every part, allowing leaf attachments without edge collisions. The concern is a proof gap, not a demonstrated counterexample.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies completely independent spanning trees (CIST) in split graphs. For a split graph G=(D∪I,E) it defines the associated hypergraph H(G) with vertex set D and hyperedges N(x), x∈I. It proves that k CIST in G imply a panchromatic k-coloring of H(G) (Theorem 4) and that a bipanchromatic k-coloring of H(G) implies k CIST in G (Theorem 5). It introduces the unique-color parameter α_k(H(G)) and derives lower bounds (Theorem 6) and an upper bound (Theorem 7), yielding the main bound χ2p(H(G)) ≤ M ≤ χ2p(H(G))+1 for the maximum number M of CIST (Theorem 8). It then proves that bipanchromatic k-coloring of hypergraphs is NP-complete (Theorem 9) and that k-CIST is NP-complete for split graphs (Theorem 10). The paper closes with ILP formulations and Conjecture 1 relating the bipanchromatic number to the panchromatic number and α.","tokens_in":11748,"tokens_out":30766,"duration_ms":311091,"significance":"If the proof gaps noted below are repaired, the paper makes a useful contribution: it connects CIST in split graphs to hypergraph colorings in a way that yields a two-sided bound and a natural NP-completeness reduction. The NP-completeness of the two-CIST problem in split graphs is a substantive result. The paper is built on known theorems rather than ad hoc assumptions, and the central constructions are simple enough to be reparable. The ILP models are not implemented, but they are clearly presented and support the stated conjecture only as computational evidence.","major_comments":[{"comment":"The proof that a bipanchromatic k-coloring yields k CIST is not established. The cited result of Pai et al. [16] constructs CIST in K_n with two internal vertices per tree; it does not imply that an arbitrary prescribed color class of size ≥2 can serve as the internal set of a tree. If surplus vertices of a color are made leaves, a hyperedge containing only the discarded vertex of that color can lose the color, so the argument does not go through. Since Theorem 5 is used for the lower bound in Theorem 8 and for the forward direction of Theorem 10, this gap is load-bearing. The gap is repairable: by Araki's Theorem 2, any partition of the clique D into parts of size at least two is a k-CIST-partition, because B(V_i,V_j) is a complete bipartite graph K_{a,b} with a,b≥2. The extension to I also needs a rigorous check; panchromaticity gives each y∈I a neighbor in every color class, so the ch","section":"Section 3, Theorem 5"},{"comment":"The proof is garbled and incomplete. The sentence \"Let y∈I be the internal vertex of T_j in I that is adjacent to x_i2, and x_i2\" is unreadable; it is never explained how T_j is built, why x_D can cover all internal vertices of T_i, or why the resulting trees satisfy the Hasunuma condition. The proposition is used in the second part of Theorem 6; although it is not needed for Theorem 8 or Theorem 10, as stated it is a correctness gap. The statement should either be proved rigorously or demoted to a conjecture/conditional result.","section":"Section 3.2, Proposition 2"},{"comment":"The contradiction is only a sketch. The assertion that i1 and i2 \"cannot cover x1 in T2 because they are already covered by x1 in T1\" confuses vertex-disjointness with edge-disjointness; a vertex can be covered by different vertices in different trees as long as the edges are distinct. The edge-count sentence requires a case analysis of which five edges of the K_{2,2} plus x1x2 configuration can be used by two edge-disjoint spanning trees; the current one-sentence argument does not rule out configurations with an internal I-vertex in T2. Since this case supplies the upper bound M ≤ χ2p(H(G))+1 in Theorem 8, it must be completed.","section":"Section 3.3, Theorem 7, Case 2"},{"comment":"The arguments color D-vertices by the part/to the tree in which they are internal. This does not automatically produce a panchromatic coloring: a vertex y∈I may be internal in T_i while having no D-neighbor in the internal set of T_i, and D-vertices that are leaves in every tree are left uncolored in the described scheme. A correct proof should pass to the Araki k-CIST partition and verify that each hyperedge N(y) meets every part; the absence of tree components in B(V_i,V_j) is the right tool, but it is not invoked. This matters because the NP-completeness claim rests on the converse.","section":"Section 3, Theorem 4 and Section 4, Theorem 10 converse"}],"minor_comments":[{"comment":"The symbol E denotes both the edge set of G and the hyperedge set of H(G); this is standard but could be flagged to avoid ambiguity.","section":"Throughout"},{"comment":"The claim that Péterfalvi's counterexample [18] is a split graph is asserted without proof or a precise construction. Please provide the split decomposition or a reference that establishes this explicitly.","section":"Observation 1"},{"comment":"In the text \"As each vertex y1 ∈ E1 and each vertex y2 ∈ E2 is covered...\", the symbols should be I1 and I2, not E1 and E2.","section":"Theorem 10 proof"},{"comment":"The variable v_j in the binary constraint should be v_p. Also, the inference from the constraint to v_p=1 relies on the minimization objective; please make that explicit.","section":"Appendix A.3, Eq. (A.8)"},{"comment":"The heading \"Bip anchroma tick-Coloring Problem\" contains a typo; it should be \"Bipanchromatic Coloring Problem\".","section":"Section 4 heading"},{"comment":"The model sets c=χp, so the bipanchromatic number is computed only after solving the panchromatic model; this is fine but should be stated near the formulation.","section":"Appendix A.2"}],"recommendation":"major_revision","confidential_remarks":"The main theorems are probably salvageable. The key fix is to replace the Pai et al. citation in Theorem 5 with an argument based on Araki's CIST-partition theorem; the remaining proofs then need rewriting rather than new ideas. The claimed split-graph property of Péterfalvi's counterexample should be verified. Proposition 2 is currently a serious gap, though it is not needed for Theorem 8 or 10. I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know: this paper has a genuinely new idea — connecting CIST in split graphs to panchromatic and bipanchromatic colorings of the associated hypergraph — and the main results are probably true. But the proof of the central converse (Theorem 5) is not actually there, and the upper bound proof (Theorem 7) is a sketch. It deserves a serious referee, not a desk reject, but the authors have real work to do.\n\nWhat's new and good: the bipanchromatic coloring notion is a useful variant, the correspondence between split graphs and hypergraphs is clean, and the bounds χ2p ≤ M ≤ χ2p+1 plus the NP-completeness of k-CIST in split graphs are solid contributions if the proofs hold. The forward direction (CIST implies panchromatic coloring) is correct, and the reduction in Theorem 10 is structurally sound. The ILP check of the conjecture is a nice extra, and the authors are honest about counterexamples to naive converses.\n\nSoft spots, in proportion: Theorem 5 is load-bearing and it doesn't prove what it needs to. The sentence \"From the result of Pai et al., only two vertices in Kn suffice to construct each tree\" does not justify using arbitrary color classes (size ≥2) as internal vertex sets. Pai et al. give trees with exactly two internal vertices, not trees with a prescribed internal set. If you discard surplus vertices as leaves, a hyperedge with only that color's surplus vertex loses the color entirely. And the extension to the independent set I is asserted in one vague sentence — you can't just assign each vertex of I arbitrarily and claim the no-tree-component condition survives. The stress-test note is right that this is likely repairable via Araki's partition theorem, but it's not repaired here. This gap cascades: the lower bound of Theorem 8 and the yes-direction of the NP reduction both depend on it. Theorem 7, Case 2 is likewise a hand-wave that ignores possible internal vertices in I and other D vertices. Proposition 2 has a garbled sentence (\"Let y ∈ I be the internal vertex of T_j in I that is adjacent to x_i2, and x_i2\") and its construction is opaque. The no-direction of Theorem 10 also silently assumes each tree has at least one internal vertex in D; if a tree's internal set were entirely in I, the hyperedge coloring would miss a color. That's likely impossible in the constructed graph, but it needs a sentence.\n\nNone of this makes me think the central claims are false. The writing is honest, the citations are fair (including the self-citation, which is just for a small verification), and the conjecture with ILP support is a reasonable research direction. But as it stands, the paper's main theorems are not proven to the standard implied.\n\nRecommendation: send it to peer review, but with explicit instructions to the authors to prove Theorem 5 properly (Araki's partition characterization is the right tool), justify the I-extension, fix the upper-bound argument, and clean up Proposition 2. If those pieces come back in a revision, this will be a useful paper for the graph-theory and fault-tolerance communities.","headline":"Genuinely new bridge between CIST in split graphs and hypergraph colorings, but the key converse theorem is under-proved and the upper bound is a sketch; the results are likely true and worth refereeing, but the paper needs a real revision.","tokens_in":12253,"tokens_out":15308,"would_cite":true,"duration_ms":144821,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","05C15","05C65","68Q17","05C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that the maximum number of completely independent spanning trees in a split graph is either the bipanchromatic number of its associated hypergraph or that number plus one, and proves that deciding whether two such trees exi","keywords":["completely independent spanning trees","split graphs","hypergraph coloring","panchromatic coloring","bipanchromatic coloring","NP-completeness","CIST-partition","spanning trees"],"falsifier":"Run the paper's own ILP check for CIST existence on split graphs whose associated hypergraphs admit a bipanchromatic 2-coloring; if any such graph fails to have two CIST, the main bridge theorem and the NP-completeness reduction are refuted. A concrete starting point is to generate small random hypergraphs, test bipanchromatic 2-colorability with the appendix ILP, build the corresponding split graphs, and verify the CIST-partition condition.","tokens_in":11254,"feed_emoji":"🌲","tokens_out":9725,"duration_ms":72696,"temperature":0.7,"pith_summary":"Split graphs are graphs whose vertices split into a clique and an independent set. This paper ties the existence of completely independent spanning trees (CIST) in such graphs to a hypergraph coloring problem: each split graph has an associated hypergraph on the clique vertices, with the neighborhoods of the independent vertices as hyperedges. The authors prove that k CIST imply a panchromatic k-coloring of that hypergraph, and that a strengthened 'bipanchromatic' k-coloring (each color appears at least twice) guarantees k CIST. As a result, the maximum number of CIST is either the bipanchromatic number or one more. They also show that deciding whether two CIST exist is NP-complete, and conjecture an exact formula relating the bipanchromatic and panchromatic numbers of hypergraphs, supported by computational experiments.","feed_headline":"Finding two independent spanning trees in split graphs is NP-complete","feed_subtitle":"The maximum number of such trees is within one of a hypergraph coloring number, and deciding if two exist is already hard.","key_machinery":"The carrying object is the associated hypergraph H(G): its vertices are the clique vertices D, and each independent vertex x contributes a hyperedge equal to its neighborhood N_G(x) in D. The argument runs through two coloring notions — panchromatic (every hyperedge meets every color) and the newly introduced bipanchromatic (panchromatic with every color used at least twice) — together with the CIST-partition characterization of completely independent spanning trees, which reduces tree-disjointness to a combinatorial condition on a vertex partition. The bridge theorem says bipanchromatic k-colorings of H(G) produce k CIST in G, while k CIST in G force only panchromatic k-colorings of H(G).","core_discovery":"The central discovery is a two-sided bridge between split graphs and hypergraphs. On one side, any k completely independent spanning trees of a split graph G force a panchromatic k-coloring of the associated hypergraph H(G): the k parts of the CIST partition give k colors that must all appear in every neighborhood hyperedge. On the other side, if H(G) has a bipanchromatic k-coloring — a panchromatic coloring with every color used at least twice — then G has k CIST, built by making each color class the internal vertices of one spanning tree inside the clique and attaching every independent vertex as a leaf to all trees. From these two directions the paper derives the tight bound chi2p(H(G)) ≤","pith_inferences":["The paper's NP-completeness reduction suggests that the computational hardness of CIST is inherited from hypergraph coloring; one may expect k-CIST to remain NP-complete for split graphs for every fixed k ≥ 2, paralleling the known hardness of panchromatic k-coloring.","If Conjecture 1 is true, then the bipanchromatic number is purely a function of panchromatic colorings, and the CIST problem in split graphs becomes algorithmically easier: one could compute M by solving a single panchromatic-coloring optimization rather than a specialized tree problem.","The new bipanchromatic coloring concept might be useful beyond split graphs: any graph class whose CIST problem can be encoded via hypergraphs (e.g., chordal graphs or other dense classes) could inherit similar bounds and hardness results.","A computational search for counterexamples to Conjecture 1 (beyond the 100 random hypergraphs tested) is a direct way to test the paper's main open question; the conjecture's failure would weaken but not destroy the main bounds."],"forward_implications":["If the bounds hold, computing the bipanchromatic number of the associated hypergraph determines the maximum number of CIST in a split graph up to an additive error of one.","Since the existence of two CIST is NP-complete even on split graphs, there is no polynomial algorithm for this case unless P = NP, and the reduction gives a way to produce hard instances from hypergraph colorability.","The sufficient condition via bipanchromatic colorings yields two CIST in split graphs that are not Hamiltonian and do not satisfy the earlier degree/size conditions, so the class of split graphs known to have two CIST is larger than previously shown.","If Conjecture 1 is true, the maximum number of CIST in a split graph is expressed exactly in terms of the panchromatic number and the minimum number of unique colors in a panchromatic coloring of its hypergraph.","The ILP formulations for panchromatic and bipanchromatic coloring (in the appendix) give a practical way to search for CIST in split graphs and to test the conjecture on larger instances."],"fun_headline_variants":["Deciding 2 independent spanning trees in split graphs is NP-complete","Split graphs: existence of 2 CIST is NP-complete","Hypergraph coloring links to CIST: two-tree case NP-hard","Split graphs vs hypergraphs: 2 independent trees hard"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof that a bipanchromatic coloring always yields the claimed trees assumes that in a complete graph any color class of at least two vertices can be turned into the internal vertices of one spanning tree while every other vertex is a leaf — an assertion supported by a one-line citation rather than by a verification for arbitrary color class sizes and independent-set attachments.","fun_headline_variants_meta":{"raw":{"variants":["Deciding 2 independent spanning trees in split graphs is NP-complete","Split graphs: existence of 2 CIST is NP-complete","Hypergraph coloring links to CIST: two-tree case NP-hard","Split graphs vs hypergraphs: 2 independent trees hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000978,"raw_usage":{"total_tokens":3946,"prompt_tokens":652,"completion_tokens":3294,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":396,"completion_tokens_details":{"reasoning_tokens":3220}},"tokens_in":396,"tokens_out":3294,"duration_ms":20277,"temperature":1.0,"reasoning_tokens":3220,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T15:48:29.968550+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the paper's own ILP check for CIST existence on split graphs whose associated hypergraphs admit a bipanchromatic 2-coloring; if any such graph fails to have two CIST, the main bridge theorem and the NP-completeness reduction are refuted. A concrete starting point is to generate small random hypergraphs, test bipanchromatic 2-colorability with the appendix ILP, build the corresponding split graphs, and verify the CIST-partition condition.","supporting_citations":[],"review_version":1}