A new minimal chordal completion

Abstract

In this paper, we present a minimal chordal completion $G^{\ast }$ of a graph $G$ satisfying the inequality $\omega (G^{\ast })-\omega (G)\le 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 $\chi$-bounded class by adding to it the family of graphs with bounded non-chordality indices.