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

Search

Interval incidence coloring of bipartite graphs

Abstract

In this paper we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number (χii) for bipartite graphs χii≤2Δ, and we prove that χii=2Δ holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e. we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic bipartite graphs. We also study the problem for bipartite graphs with Δ=4 and we show that 5-coloring is easy and 6-coloring is hard (NP-complete). Moreover, we construct an O(nΔ^3.5logΔ) time optimal algorithm for trees.

Citations

  • 3

    CrossRef

  • 0

    Web of Science

  • 4

    Scopus

Cite as

Full text

download paper
downloaded 1 times
Publication version
Accepted or Published Version
DOI:
Digital Object Identifier (open in new tab) 10.1016/j.dam.2013.10.007
License
Copyright (2013 Elsevier B.V.)

Keywords

Details

Category:
Articles
Type:
artykuł w czasopiśmie wyróżnionym w JCR
Published in:
DISCRETE APPLIED MATHEMATICS no. 166, pages 131 - 140,
ISSN: 0166-218X
Language:
English
Publication year:
2014
Bibliographic description:
Janczewski R., Małafiejska A., Małafiejski M.: Interval incidence coloring of bipartite graphs// DISCRETE APPLIED MATHEMATICS. -Vol. 166, (2014), s.131-140
DOI:
Digital Object Identifier (open in new tab) 10.1016/j.dam.2013.10.007
Verified by:
Gdańsk University of Technology

seen 111 times

Recommended for you

Meta Tags