On Efficient coloring of chordless graphs

• Autorzy: Janczewski R. , Małafiejski M.
• Języki publikacji: EN

Abstrakty

EN

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 pathchordless (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.

Słowa kluczowe

EN

vertex coloring; chordless graphs; chromatic number

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Decision Making in Manufacturing and Services
• Rocznik: 2009
• Tom: Vol. 3, no. 1-2
• Strony: 5--14
• Opis fizyczny: Bibliogr. [2] poz., rys.

Twórcy

autor

Janczewski R.

• Department of Algorithms and System Modelling, Gdańsk University of Technology, Poland

autor

Małafiejski M.

• Department of Algorithms and System Modelling, Gdańsk University of Technology, Poland

Bibliografia

• Brandstädt, A., Le, V.B., Spinrad, J.P. (1999). Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia.
• Matula, D.W., Marble, G., Isaacson, D. (1972). Graph coloring algorithms, in: Graph Theory and Computing, Academic Press, New York, pp. 109–122.