pipette
ESEspañol

On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs

Mohammed Lalou, Nader Mbarek, Abdallah Skender, Olivier Togni

Preprint

In the authors' words

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.

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 11 pages, 4 figures