Małafiejska, Anna ;
Małafiejski, Michał ;
Ocetkiewicz, Krzysztof M. ;
Pastuszak, Krzysztof
Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees
Abstract
An edge coloring of a graph G is called interval edge coloring if for each v ∈ V(G) the set of colors on edges incident to v forms an interval of integers. A graph G is interval colorable if there is an interval coloring of G. For an interval colorable graph G, by the interval chromatic index of G, denoted by χ'_i(G), we mean the smallest number k such that G is interval colorable with k colors. A bipartite graph G is called (α,β)biregular if each vertex in one part has degree α and each vertex in the other part has degree β. A graph G is called (α*,β*)bipartite if G is a subgraph of an (α,β)biregular graph and the maximum degree in one part is α and the maximum degree in the other part is β.
In the paper we study the problem of interval edge colorings of (k*,2*)bipartite graphs, for k ∈ {3,4,5}, and of (5*,3*)bipartite graphs. We prove that every (5*,2*)bipartite graph admits an interval edge coloring using at most 6 colors, which can be found in O(n^{3/2}) time, and we prove that an interval edge 5coloring of a (5*,2*)bipartite graph can be found in O(n^{3/2}) time, if it exists. We show that every (4^*,2^*)bipartite graph admits an interval edge 4coloring, which can be found in O(n) time. The two following problems of interval edge coloring are known to be NPcomplete: 6coloring of (6,3)biregular graphs (Asratian and Casselgren (2006)) and 5coloring of (5*,5*)bipartite graphs (Giaro (1997)). In the paper we prove NPcompleteness of 5coloring of (5*,3*)bipartite graphs.
BibTeX  Entry
@InProceedings{malafiejska_et_al:LIPIcs.ISAAC.2021.26,
author = {Ma{\l}afiejska, Anna and Ma{\l}afiejski, Micha{\l} and Ocetkiewicz, Krzysztof M. and Pastuszak, Krzysztof},
title = {{Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {26:126:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772143},
ISSN = {18688969},
year = {2021},
volume = {212},
editor = {Ahn, HeeKap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15459},
URN = {urn:nbn:de:0030drops154596},
doi = {10.4230/LIPIcs.ISAAC.2021.26},
annote = {Keywords: interval edge coloring, biregular graphs, coloring algorithm}
}
30.11.2021
Keywords: 

interval edge coloring, biregular graphs, coloring algorithm 
Seminar: 

32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Issue date: 

2021 
Date of publication: 

30.11.2021 