2018/10/11 by Jihoon Choi, Choi, Jihoon, Soogang Eoh +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Software Testing and Debugging Techniques
paper · pdf · doi:10.48550/arxiv.1810.05280
openalex publication_date 2018/10/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we present a minimal chordal completion G^* of a graph G satisfying the inequality ω(G^*) - ω(G) ≤ i(G) for the non-chordality index i(G) of G. In terms of our chordal completions, we partially settle the Hadwiger conjecture and the Erdős-Faber-Lovász Conjecture, and extend the known χ-bounded class by adding to it the family of graphs with bounded non-chordality indices.