Abstract
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 N P-complete, and they asked if χii(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.
Citations
-
1
CrossRef
-
0
Web of Science
-
1
Scopus
Authors (2)
Cite as
Full text
download paper
downloaded 42 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.7151/dmgt.1962
- License
- open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
Discussiones Mathematicae Graph Theory
no. 37,
pages 427 - 441,
ISSN: 1234-3099 - Language:
- English
- Publication year:
- 2017
- Bibliographic description:
- Małafiejska A., Małafiejski M.: Interval incidence coloring of subcubic graphs// Discussiones Mathematicae Graph Theory. -Vol. 37, (2017), s.427-441
- DOI:
- Digital Object Identifier (open in new tab) 10.7151/dmgt.1962
- Verified by:
- Gdańsk University of Technology
seen 146 times