Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Decision Making in Manufacturing and Services

1 2009

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: chordless graphs

Sortuj według:

Ogranicz wyniki do:

On Efficient coloring of chordless graphs

Janczewski R., Małafiejski M.

Decision Making in Manufacturing and Services

2009

Vol. 3, no. 1-2

5-14

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.