pipette
ENEnglish

On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs

Mohammed Lalou, Nader Mbarek, Abdallah Skender, Olivier Togni

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 11 pages, 4 figures