On Efficient Coloring of Chordless Graphs

We are given a simple graph G = ( V , E ). Any edge e ∈ E is a chord in a path P ⊆ G (cycle C ⊆ G ) iff a graph obtained by joining e to path P (cycle C ) has exactly two vertices of degree 3. A class of graphs without any chord in paths (cycles) we call path-chordless ( cycle-chordless ). We will prove that recognizing and coloring of these graphs can be done in O ( n 2 ) and O ( n ) time, respectively. Our study was motivated by a wide range of applications of the graph coloring problem in coding theory, time tabling and scheduling, frequency assignment, register allocation and many other areas.