On Efficient Coloring of Chordless Graphs
Decision Making in Manufacturing and Services · 2009
DOI: 10.7494/dmms.2009.3.2.5 ↗Kurz gefasst
Fachartikel in der Zeitschrift Decision Making in Manufacturing and Services, 2009. Verfasst von Robert Janczewski und 1 weiteren Autor:innen. Die Arbeit nennt 2 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Janczewski, R., & Małafiejski, M. (2009). On Efficient Coloring of Chordless Graphs. Decision Making in Manufacturing and Services. https://doi.org/10.7494/dmms.2009.3.2.5
Vancouver
Janczewski R, Małafiejski M. On Efficient Coloring of Chordless Graphs. Decision Making in Manufacturing and Services. 2009. doi:10.7494/dmms.2009.3.2.5
BibTeX
@article{Janczewski2009,
author = {Janczewski, Robert and Małafiejski, Michał},
title = {On Efficient Coloring of Chordless Graphs},
journal = {Decision Making in Manufacturing and Services},
year = {2009},
doi = {10.7494/dmms.2009.3.2.5}
}
EUVIMED