Pith. sign in

REVIEW 4 major objections 6 minor 23 references

Completely Independent Spanning Trees in Split Graphs: Structural Properties and Complexity

T0 review · 4 major / 6 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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

desk verdict 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. read the letter →

arxiv 2512.15486 v2 pith:HKLRR7FS submitted 2025-12-17 math.CO cs.DM

Mohammed Lalou , Nader Mbarek , Abdallah Skender , Olivier Togni This is my paper · ORCID
classification math.COcs.DM MSC 05C8505C1505C6568Q1705C05
keywords completelyindependentspanningtreessplitgraphshypergraphcoloringpanchromaticbipanchromaticNP-completenessCIST-partition
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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).

What would settle it

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.

Watch

Extended reading notes

Core claim

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)) ≤

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

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 α.

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 (4)
  1. [Section 3, Theorem 5] 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
  2. [Section 3.2, Proposition 2] 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.
  3. [Section 3.3, Theorem 7, Case 2] 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.
  4. [Section 3, Theorem 4 and Section 4, Theorem 10 converse] 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.
minor comments (6)
  1. [Throughout] 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.
  2. [Observation 1] 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.
  3. [Theorem 10 proof] 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.
  4. [Appendix A.3, Eq. (A.8)] 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.
  5. [Section 4 heading] The heading "Bip anchroma tick-Coloring Problem" contains a typo; it should be "Bipanchromatic Coloring Problem".
  6. [Appendix A.2] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No material circularity: the main results are established from external theorems (Araki, Pai et al., Property B), and the only self-citation is non-load-bearing; the Pai step is a repairable rigor gap, not circular.

full rationale

No circularity is found in the derivation chain. Theorem 4 is a direct translation of Araki's CIST-partition characterization. Theorem 5 uses the external result of Pai et al. [16] plus Araki's Theorem 2 to lift a bipanchromatic coloring to CIST; the lower bound in Theorem 8 and the yes-direction of Theorem 10 genuinely depend on that external theorem rather than on the paper's own definitions. The upper bound in Theorem 7 is argued directly from the existence of CIST and the definition of the bipanchromatic number, not from the claim being proved. The NP-completeness reductions are standard reductions from known Property-B/panchromatic coloring problems. The only same-team citation, [15], is used to verify the small counterexample in Figure 2; that example is motivating, not load-bearing. Two rigor caveats are worth flagging explicitly, but they are correctness issues, not circularity. First, the sentence in Theorem 5 citing Pai et al. does not by itself justify arbitrary prescribed internal-vertex sets of size greater than two (Pai et al. construct trees with two internal vertices), and the statement that each vertex of I is 'assigned arbitrarily' to one of the sets needs a fuller proof of the CIST-partition conditions. This gap appears repairable through Araki's Theorem 2, since any partition of the clique into parts of size at least two is a k-CIST-partition of the complete graph. Second, the use of [7] for panchromatic k-colorability is terse, but the k=2 case reduces to Property-B and the two-copy construction in Theorem 9 is explicit. Neither caveat makes a claimed result equal to its input by construction, renames a known result, or imports the paper's conclusion through a self-citation.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper defines a new coloring notion, bipanchromatic coloring, but this is a definition built from standard hypergraph coloring, not an invented entity. The central claims rest on external theorems and on one under-specified application of Pai et al.'s result; there are no free parameters and no ad hoc entities.

assumptions (5)
  • standard math Araki's theorem: a graph admits k CIST iff it has a k-CIST partition (Theorem 2).
    Used as the bridge between CIST and partitions throughout Sections 3 and 4.
  • standard math Hasunuma's characterization: CIST iff edge-disjoint and every vertex is internal in at most one tree (Theorem 1).
    Used to verify membership in NP in Theorem 10.
  • domain assumption Pai et al. [16]: K_n admits CIST with only two internal vertices per tree, for each n>=4.
    Invoked in Theorem 5 to turn color classes of size at least 2 into CIST inside the clique D; the paper does not give the construction or prove it works for arbitrary color classes.
  • standard math Property B, and panchromatic k-coloring by extension, is NP-complete.
    Used as the source problem for the reductions in Theorems 9 and 10; the paper explicitly notes only the k=2 case.
  • domain assumption Péterfalvi's counterexample to Hasunuma's conjecture is a split graph whose corresponding hypergraph is not k-colorable.
    Observation 1 asserts this without proof. It is peripheral to the main results but is presented as evidence for the contrapositive of Theorem 4.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Completely Independent Spanning Trees in Split Graphs: Structural Properties and Complexity." pith.science (2026). https://pith.science/paper/HKLRR7FS

@misc{pith2026251215486,
  author       = {Pith},
  title        = {Pith review of: Completely Independent Spanning Trees in Split Graphs: Structural Properties and Complexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HKLRR7FS}},
  note         = {Machine review of arXiv:2512.15486}
}
read the original abstract

We study completely independent spanning trees (CIST), \textit{i.e.}, trees that are both edge-disjoint and internally vertex-disjoint, in split graphs. We establish a correspondence between the existence of CIST in a split graph and some types of hypergraph colorings (panchromatic and bipanchromatic colorings) of its associated hypergraph, allowing us to obtain lower and upper bounds on the number of CIST. Using these relations, we prove that the problem of the existence of two CIST in a split graph is NP-complete. Finally, we formulate a conjecture on the bipanchromatic number of a hypergraph related to the results obtained for the number of CIST.

Figures

Figures reproduced from arXiv: 2512.15486 by the authors.

Figure 1
Figure 1. A split graph and its corresponding hypergraph [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. A split graph without 3 CIST whose corresponding hypergraph is panchromatically 3-colorable i = 1, 2, . . . , k is assigned to the set of internal vertices of the tree Ti denoted Vi . From the result of Pai et al. [16], only two vertices in Kn suffice to construct each tree for each n ≥ 4. As H(G) is bipanchromatically k-colorable, the number of internal vertices per tree is at least two. Since the Ti are CIST in D,… view at source ↗
Figure 3
Figure 3. A split graph having 2 CIST while not satisfying the conditions of Theorem 3 6 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: shows a graph with two completely independent spanning trees, yet its corresponding hypergraph is not bipanchromatically 2-colorable [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: A split graph G where xD is adjacent to all vertices of I but its color is not unique in some of the panchromatic 2-colorings of H(G) Lemma 2. Let k ≥ 2. Let G = (D ∪ I, E) be a split graph such that H(G) is k-uniform. Let xD be a vertex of D and φ be a panchromatic k-…
Figure 6
Figure 6. Figure 6: Configuration of proof of Proposition 1 for [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]
Figure 7
Figure 7. Figure 7: A split graph without 3 CIST whose corresponding hypergraph is not 3-uniform xD can cover xi1 and is covered by xi2 . Also, xD covers all internal vertices of Ti non-adjacent to y, and y covers the remaining internal vertices of Ti (see [PITH_FULL_IMAGE:figures/full_f…
Figure 8
Figure 8. Figure 8: Illustration of the proof of Proposition 2 [PITH_FULL_IMAGE:figures/full_fig_p010_8.png]
Figure 9
Figure 9. Figure 9: Configuration of proof of Theorem 7 leading to a contradiction (Case 2) [PITH_FULL_IMAGE:figures/full_fig_p012_9.png]
Figure 10
Figure 10. Figure 10: Hypergraphs H and H′ Now, we consider the k CIST problem in split graphs; its recognition version is given by: 13 [PITH_FULL_IMAGE:figures/full_fig_p013_10.png]
Figure 11
Figure 11. Figure 11: A polynomial-time reduction from the panchromatic [PITH_FULL_IMAGE:figures/full_fig_p015_11.png]
Figure 12
Figure 12. Figure 12: A mapping of a panchromatic 2-coloring solution in H to a 2-CIST solution in G′ all panchromatic χp(H)-colorings of H. As bipanchromatic coloring is a new type of coloring, it would be useful to prove a stronger result relating the panchromatic and bipanchromatic numb…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 8 canonical work pages

  1. [16]

    Pai, S.-M

    K.-J. Pai, S.-M. Tang, J.-M. Chang, and J.-S. Yang. Completely Independent Spanning Trees on Complete Graphs, Complete Bipartite Graphs and Com- plete Tripartite Graphs. InAdvances in Intelligent Systems and Applications - Volume 1, pages 107–113. Springer, 2013. doi: 10.1007/978-3-642-35452-6 _13

    work page doi:10.1007/978-3-642-35452-6 2013

  2. [1]

    T. Araki. Dirac’s Condition for Completely Independent Spanning Trees. Journal of Graph Theory, 77(3):171–179, 2014. doi: 10.1002/jgt.21780

    doi:10.1002/jgt.21780 2014

  3. [2]

    Araki, M

    T. Araki, M. Matsushita, and Y. Otachi. Completely independent spanning trees in (partial) k-trees.Discussiones Mathematicae Graph Theory, 35(3): 427, 2015. doi: 10.7151/dmgt.1806

    doi:10.7151/dmgt.1806 2015

  4. [3]

    F. Bao, Y. Funyu, Y. Hamada, and Y. Igarashi. Reliable broadcasting and se- curedistributinginchannelnetworks. InProceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN’97), pages 472–478, 1997. doi: 10.1109/ISPAN.1997.645139

    arXiv 1997

  5. [4]

    X. Chen, Q. Liu, and X. Yang. Two completely independent spanning trees of split graphs.Discrete Applied Mathematics, 340:76–78, Dec. 2023. doi: 10.1016/j.dam.2023.07.001

    doi:10.1016/j.dam.2023.07.001 2023

  6. [5]

    Cheng, D

    B. Cheng, D. Wang, and J. Fan. Independent spanning trees in networks: A survey.ACM Computing Surveys, 55(14S):1–29, 2023. doi: 10.1145/3591110

    doi:10.1145/3591110 2023

  7. [6]

    G. Fan, Y. Hong, and Q. Liu. Ore’s condition for completely independent spanning trees.Discrete Applied Mathematics, 177:95–100, Nov. 2014. doi: 10.1016/j.dam.2014.06.002

    doi:10.1016/j.dam.2014.06.002 2014

  8. [7]

    M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979

    1979

Show all 23 references
  1. [8]

    Hasunuma

    T. Hasunuma. Completely independent spanning trees in the underlying graph of a line digraph.Discrete Mathematics, 234(1):149–157, 2001. doi: 10.1016/S0012-365X(00)00377-0

    2001 doi

  2. [9]

    Hasunuma

    T. Hasunuma. Completely Independent Spanning Trees in Maximal Planar Graphs. InGraph-Theoretic Concepts in Computer Science, pages 235–245. Springer, 2002. doi: 10.1007/3-540-36379-3_21. 17

    2002 doi

  3. [10]

    Hasunuma and C

    T. Hasunuma and C. Morisaka. Completely independent spanning trees in torus networks.Networks, 60(1):59–69, 2012. doi: 10.1002/net.20460

    2012 doi

  4. [11]

    Hong and H

    X. Hong and H. Zhang. A Hamilton sufficient condition for completely in- dependent spanning tree.Discrete Applied Mathematics, 279:183–187, May

  5. [12]

    Kostochka

    A. Kostochka. Color-Critical Graphs and Hypergraphs with Few Edges: A Survey. InMore Sets, Graphs and Numbers: A Salute to Vera Sós and András Hajnal, pages 175–197. Springer, 2006. doi: 10.1007/978-3-540-32439-3_9

    2006 doi

  6. [13]

    N. Liu, Y. Zhang, and W. Fan. Construction of Completely Independent Spanning Tree Based on Vertex Degree. InParallel and Distributed Com- puting, Applications and Technologies, pages 94–103. Springer International Publishing, 2021. doi: 10.1007/978-3-030-69244-5_8

    2021 doi

  7. [14]

    Ma and J

    J. Ma and J. Cai. Fan’s condition for completely independent spanning trees. Feb. 2025. doi: 10.48550/arXiv.2502.11522

    2025 doi arXiv

  8. [15]

    Moinet, B

    A. Moinet, B. Darties, N. Gastineau, J.-L. Baril, and O. Togni. Completely independent spanning trees for enhancing the robustness in ad-hoc Networks. In2017 IEEE 13th International Conference on Wireless and Mobile Com- puting, Networking and Communications (WiMob), pages 63–...

    2017

  9. [17]

    Pai, J.-S

    K.-J. Pai, J.-S. Yang, S.-C. Yao, S.-M. Tang, and J.-M. Chang. Com- pletely Independent Spanning Trees on Some Interconnection Networks.IE- ICE Transactions on Information, E97-D(9):2514–2517, Sept. 2014. doi: 10.1587/transinf.2014EDL8079

    2014 doi

  10. [18]

    Péterfalvi

    F. Péterfalvi. Two counterexamples on completely independent spanning trees.Discrete Mathematics, 312(4):808–810, Feb. 2012. doi: 10.1016/j.di sc.2011.11.015

    2012 doi

  11. [19]

    Qin, R.-X

    X.-W. Qin, R.-X. Hao, and J. Wu. Construction of Dual-CISTs on an Infinite Class of Networks.IEEE Transactions on Parallel and Distributed Systems, 33(8):1902–1910, Aug. 2022. doi: 10.1109/TPDS.2021.3132412. 18

    1902

  12. [20]

    A. M. Raigorodskii and D. A. Shabanov. The Erdős-Hajnal problem of hy- pergraph colouring, its generalizations, and related problems.Russian Math- ematical Surveys, 66(5):933–1002, Oct. 2011. doi: 10.1070/RM2011v066n0 5ABEH004764

    2011 doi

  13. [21]

    Tseng, S.-Y

    Y.-C. Tseng, S.-Y. Wang, and C.-W. Ho. Efficient broadcasting in wormhole- routed multicomputers: a network-partitioning approach.IEEE Transactions on Parallel and Distributed Systems, 10(1):44–61, 1999. doi: 10.1109/71.744 837

    1999 doi

  14. [22]

    J. Yuan, R. Zhang, and A. Liu. Degree Conditions for Completely Indepen- dent Spanning Trees of Bipartite Graphs.Graphs and Combinatorics, 38(6): 179, Oct. 2022. doi: 10.1007/s00373-022-02585-w. Appendices A Linear modeling LetH= (V,E)be a hypergraph such that|D|=nand|I|=m. Le...

    2022 doi

  15. [2020]

    doi: 10.1016/j.dam.2019.08.013

    2019 doi

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.