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.
@article{bwmeta1.element.doi-10_7151_dmgt_1962,
author = {Anna Ma\l afiejska and Micha\l\ Ma\l afiejski},
title = {Interval Incidence Coloring of Subcubic Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {37},
year = {2017},
pages = {427-441},
zbl = {06705138},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1962}
}
Anna Małafiejska; Michał Małafiejski. Interval Incidence Coloring of Subcubic Graphs. Discussiones Mathematicae Graph Theory, Tome 37 (2017) pp. 427-441. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1962/