Czasopismo
Tytuł artykułu
Autorzy
Warianty tytułu
Języki publikacji
Abstrakty
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
Rocznik
Tom
Numer
Strony
5--14
Opis fizyczny
Twórcy
autor
- Gdańsk University of Technology
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000171387695