Interval incidence coloring of subcubic graphs - Publication - Bridge of Knowledge

Search

Interval incidence coloring of subcubic graphs

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

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 97 times

Recommended for you

Meta Tags