TY - JOUR
AU - Janczewski, Robert
AU - Małafiejski, Michał
PY - 2009/12/21
Y2 - 2024/05/29
TI - On Efficient Coloring of Chordless Graphs
JF - Decision Making in Manufacturing and Services
JA - DMMS
VL - 3
IS - 2
SE -
DO - 10.7494/dmms.2009.3.2.5
UR - https://journals.agh.edu.pl/dmms/article/view/544
SP - 5-14
AB - <p>We are given a simple graph <em>G</em> = (<em>V</em>, <em>E</em>). Any edge <em>e</em> ∈ <em>E</em> is a <em>chord</em> in a path <em>P</em> ⊆ <em>G</em> (cycle <em>C</em> ⊆ <em>G</em>) iff a graph obtained by joining <em>e</em> to path <em>P</em> (cycle <em>C</em>) has exactly two vertices of degree 3. A class of graphs without any chord in paths (cycles) we call <em>path-chordless</em> (<em>cycle-chordless</em>). We will prove that recognizing and coloring of these graphs can be done in <em>O</em>(<em>n</em><small><small><sup>2</sup></small></small>) and <em>O</em>(<em>n</em>) 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.</p>
ER -