Wyszukiwarka
Abstrakt
In this paper we introduce a concept of interval incidence coloring of graphs and survey its general properties including lower and upper bounds on the number of colors. Our main focus is to determine the exact value of the interval incidence coloring number χii for selected classes of graphs, i.e. paths, cycles, stars, wheels, fans, necklaces, complete graphs and complete k-partite graphs. We also study the complexity of the interval incidence coloring problem for subcubic graphs for which we show that the problem of determining whether χii≤4 can be solved in polynomial time whereas χii≤5 is NP-complete
Cytowania
-
1
CrossRef
-
0
Web of Science
-
2
Scopus
Autorzy (3)
Cytuj jako
Pełna treść
pobierz publikację
pobrano 36 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2014.03.006
- Licencja
- Copyright (2014 Elsevier B.V)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
DISCRETE APPLIED MATHEMATICS
nr 182,
strony 73 - 83,
ISSN: 0166-218X - Język:
- angielski
- Rok wydania:
- 2015
- Opis bibliograficzny:
- Janczewski R., Małafiejska A., Małafiejski M.: Interval incidence graph coloring// DISCRETE APPLIED MATHEMATICS. -Vol. 182, (2015), s.73-83
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2014.03.006
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 159 razy