Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This is the authors' abstract. We don't add key points for this paper.

A finite undirected graph is called chordal if every simple circuit has a chord. Given a chordal graph, we present, ways for constructing efficient algorithms for finding a minimum coloring, a minimum covering by cliques, a maximum clique, and a maximum independent set. The proofs are based on a theorem of D. Rose [3] that a finite graph is chordal if and only if it has some special orientation called an R-orientation. In the last part of this paper we prove that an infinite graph is chordal if and only if it has an R-orientation.