2022/10/01 by Clément Dallard, Blas Fernández, Dallard, Clément +7
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2210.00383
Katona and Varga showed that for any rational number t ∈ (1/2,1], no chordal graph is minimally t-tough, while Katona and Khan characterized all minimally t-tough, chordal graphs with t ≤ 1/2. We conjecture that no chordal graph is minimally t-tough for any t>1 and prove several results supporting the conjecture. In particular, we show that for any t>1/2, no strongly chordal graph is minimally t-tough%, no split graph is minimally t-tough, and no chordal graph with a universal vertex is minimally t-tough.