Repository logo

Browsing by Subject "chordless graphs"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • thumbnail.journal.alt
    Item type:Article, Access status: Open Access ,
    On efficient coloring of chordless graphs
    (Wydawnictwa AGH, 2009) Janczewski, Robert; Małafiejski, Michał
    We are given a simple graph $G=(V,E)$. Any edge $e \in E$ is a chord in a path $P \subseteq G$ (cycle $C \subseteq 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 <i>pathchordless</i> (<i>cycle-chordless</i>). We will prove that recognizing and coloring of these graphs can be done in $O(n^{2})$ 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.