Czasopismo
Tytuł artykułu
Autorzy
Warianty tytułu
Języki publikacji
Abstrakty
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
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
427-441
Opis fizyczny
Daty
wydano
2017-05-01
otrzymano
2016-02-09
poprawiono
2017-01-12
zaakceptowano
2017-01-12
online
2017-04-01
Twórcy
autor
- Department of Probability Theory and Biomathematics Faculty of Physics and Applied Mathematics Gdańsk University of Technology, Narutowicza 11/12, Gdańsk,, anna@animima.org
autor
- Department of Algorithms and System Modeling Faculty of Electronics, Telecommunications and Informatics Gdańsk University of Technology, Narutowicza 11/12, Gdańsk,, michal@animima.org
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1962