Interval Incidence Coloring of Subcubic Graphs

Anna Małafiejska, and Michał Małafiejski. "Interval Incidence Coloring of Subcubic Graphs." Discussiones Mathematicae Graph Theory 37.2 (2017): 427-441. <http://eudml.org/doc/287979>.

@article{AnnaMałafiejska2017,
abstract = {In this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is NP-complete, and they asked if Xii(G) ≤ 2Δ(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with Δ(G) = 3.},
author = {Anna Małafiejska, Michał Małafiejski},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {interval incidence coloring; incidence coloring; subcubic graph},
language = {eng},
number = {2},
pages = {427-441},
title = {Interval Incidence Coloring of Subcubic Graphs},
url = {http://eudml.org/doc/287979},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Anna Małafiejska
AU - Michał Małafiejski
TI - Interval Incidence Coloring of Subcubic Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 2
SP - 427
EP - 441
AB - In this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is NP-complete, and they asked if Xii(G) ≤ 2Δ(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with Δ(G) = 3.
LA - eng
KW - interval incidence coloring; incidence coloring; subcubic graph
UR - http://eudml.org/doc/287979
ER -