Completely Independent Spanning Trees in Split Graphs: Structural Properties and Complexity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914205613948928 |
|---|---|
| author | Lalou, Mohammed Mbarek, Nader Skender, Abdallah Togni, Olivier |
| author_facet | Lalou, Mohammed Mbarek, Nader Skender, Abdallah Togni, Olivier |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_15486 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Completely Independent Spanning Trees in Split Graphs: Structural Properties and Complexity Lalou, Mohammed Mbarek, Nader Skender, Abdallah Togni, Olivier Combinatorics Discrete Mathematics 05C05 (Primary) 05C15, 05C65 (Secondary) G.2.2 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. |
| title | Completely Independent Spanning Trees in Split Graphs: Structural Properties and Complexity |
| topic | Combinatorics Discrete Mathematics 05C05 (Primary) 05C15, 05C65 (Secondary) G.2.2 |
| url | https://arxiv.org/abs/2512.15486 |