Search
Abstract
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
Citations
-
1
CrossRef
-
0
Web of Science
-
2
Scopus
Authors (3)
Cite as
Full text
download paper
downloaded 32 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.dam.2014.03.006
- License
- Copyright (2014 Elsevier B.V)
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
DISCRETE APPLIED MATHEMATICS
no. 182,
pages 73 - 83,
ISSN: 0166-218X - Language:
- English
- Publication year:
- 2015
- Bibliographic description:
- Janczewski R., Małafiejska A., Małafiejski M.: Interval incidence graph coloring// DISCRETE APPLIED MATHEMATICS. -Vol. 182, (2015), s.73-83
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.dam.2014.03.006
- Verified by:
- Gdańsk University of Technology
seen 156 times