Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 48 min ago
PreprintCC BY 4.0arXiv

On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs

  • Mohammed Lalou
  • Nader Mbarek
  • Abdallah Skender
  • Olivier Togni
Open at sourcePDFDOICite

Abstract

In this paper, we study the existence problem of completely independent spanning trees (CIST) in chordal graphs through appropriate hypergraph representations and their panchromatic and bipanchromatic colorings. First, we disprove a conjecture stating an exact relationship between the panchromatic number, the bipanchromatic number, and the minimum number of unique colors in an optimal panchromatic coloring of a hypergraph. Then, by relating CIST to panchromatic and bipanchromatic colorings of the associated hypergraphs, we derive structural conditions for their existence in chordal graphs and specifically strictly chordal graphs.

Related

  1. Constructing two completely independent spanning trees in dual-cubes
    Mohammed Lalou, Nader Mbarek, Abdallah Skender +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. The replica symmetric solution for hypergraph independent sets in the critical regime
    Matthew Jenssen, Will Perkins, Aditya Potukuchi +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Extremal Spanning Trees of Random Marked Graphs with Independent Edge Weights
    Ghurumuruhan Ganesan
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  4. The multiplicative Merino--Welsh inequality for chordal graphs
    Shaohan Xu, Fengming Dong, Kexiang Xu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
    François Clautiaux, Pierre Pesneau
    HALPreprintCC BY 4.0Full textGeneral mathematicsHAL

Cite

BibTeXRIS
BibTeX
@misc{lalou2026hypergraph,
  title = {{On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs}},
  author = {Mohammed Lalou and Nader Mbarek and Abdallah Skender and Olivier Togni},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.08042},
  eprint = {2610.08042},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.08042},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
AU  - Mohammed Lalou
AU  - Nader Mbarek
AU  - Abdallah Skender
AU  - Olivier Togni
PY  - 2026
DA  - 2026/10/06
PB  - arXiv
DO  - 10.48550/arxiv.2610.08042
UR  - https://arxiv.org/abs/2610.08042
AB  - In this paper, we study the existence problem of completely independent spanning trees (CIST) in chordal graphs through appropriate hypergraph representations and their panchromatic and bipanchromatic colorings. First, we disprove a conjecture stating an exact relationship between the panchromatic number, the bipanchromatic number, and the minimum number of unique colors in an optimal panchromatic coloring of a hypergraph. Then, by relating CIST to panchromatic and bipanchromatic colorings of the associated hypergraphs, we derive structural conditions for their existence in chordal graphs and specifically strictly chordal graphs.
ER  -