When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.26
URN: urn:nbn:de:0030-drops-154596
URL: https://drops.dagstuhl.de/opus/volltexte/2021/15459/
 Go to the corresponding LIPIcs Volume Portal

### Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees

 pdf-format:

### 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 5-coloring 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 4-coloring, which can be found in O(n) time. The two following problems of interval edge coloring are known to be NP-complete: 6-coloring of (6,3)-biregular graphs (Asratian and Casselgren (2006)) and 5-coloring of (5*,5*)-bipartite graphs (Giaro (1997)). In the paper we prove NP-completeness of 5-coloring 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:1--26:12},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-214-3},
ISSN =	{1868-8969},
year =	{2021},
volume =	{212},
editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},