On Efficient Coloring of Chordless Graphs
DOI:
https://doi.org/10.7494/dmms.2009.3.2.5Keywords:
vertex-coloring, chordless graphs, chromatic numberAbstract
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(n2) 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.
References
Brandstädt A., Le V.B. & Spinrad J.P. (1999). Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. Philadelphia, PA: Society for Industrial and Applied Mathematics. DOI: https://doi.org/10.1137/1.9780898719796.
Matula D.W., Marble G. & Isaacson J.D. (1972). Graph coloring algorithms. In: Read R.C. (Ed.), Graph Theory and Computing. New York: Academic Press, pp. 109–122. DOI: https://doi.org/10.1016/B978-1-4832-3187-7.50015-5.
