Answers are grounded in this paper and cite their sources.
Establishes complexity of independent spanning trees in split graphs, suggesting new hypergraph relationships.
We study completely independent spanning trees (CIST), 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.
No takes yet. Share an insight, caveat, or question.
Lalou et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: