Chordal graphs linked to new coloring conditions for spanning trees
On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
Discrete Mathematics
Summary
The paper looks at how a special kind of network, called chordal graphs, can be better understood using color-coded groups called hypergraphs. The authors show that a previously believed exact relationship about colors doesn’t always hold. They also find new rules that help check when special kinds of spanning trees, called completely independent spanning trees, exist in these networks. This could help understand complex connections more clearly.
What this means in practice
- •For network designers: Determine reliable spanning tree structures in chordal network topologies for fault-tolerant communication.
- •For database architects: Identify structural conditions to optimize query plans using chordal graph properties with novel coloring constraints.
A theory result. No direct application yet.
Authors
Mohammed Lalou, Nader Mbarek, Abdallah Skender, Olivier Togni
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.