On efficient coloring of chordless graphs

Abstract

We are given a simple graph $G=(V,E)$. Any edge $e \in E$ is a chord in a path $P \subseteq G$ (cycle $C \subseteq 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 <i>pathchordless</i> (<i>cycle-chordless</i>). 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.