On Efficient Coloring of Chordless Graphs

• Autorzy: Robert Janczewski , Michał Małafiejski
• 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. (original abstract)

Słowa kluczowe

EN

Graphs; Applications of mathematics

PL

Grafy; Zastosowanie matematyki

• Czasopismo: Decision Making in Manufacturing and Services
• Rocznik: 2009
• Tom: 3
• Numer: nr 1/2
• Strony: 5--14

Twórcy

autor

Robert Janczewski

• Gdańsk University of Technology

autor

Michał Małafiejski

• Gdańsk University of Technology

Bibliografia

• Brandstadt, 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.