Interval Incidence Coloring of Subcubic Graphs

• Autorzy: Anna Małafiejska , Michał Małafiejski
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

interval incidence coloring; incidence coloring; subcubic graph

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 2
• Strony: 427-441

Daty

wydano

2017-05-01

otrzymano

2016-02-09

poprawiono

2017-01-12

zaakceptowano

2017-01-12

online

2017-04-01

Twórcy

autor

Anna Małafiejska

• Department of Probability Theory and Biomathematics Faculty of Physics and Applied Mathematics Gdańsk University of Technology, Narutowicza 11/12, Gdańsk,

autor

Michał Małafiejski

• Department of Algorithms and System Modeling Faculty of Electronics, Telecommunications and Informatics Gdańsk University of Technology, Narutowicza 11/12, Gdańsk,

Identyfikatory

DOI

10.7151/dmgt.1962