1 Search Results for "Pastuszak, Krzysztof"

Document
DOI: 10.4230/LIPIcs.ISAAC.2021.26
Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees

Authors: Anna Małafiejska, Michał Małafiejski, Krzysztof M. Ocetkiewicz, and Krzysztof Pastuszak

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

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.
Cite as

Anna Małafiejska, Michał Małafiejski, Krzysztof M. Ocetkiewicz, and Krzysztof Pastuszak. Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 26:1-26:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.26},
  URN =		{urn:nbn:de:0030-drops-154596},
  doi =		{10.4230/LIPIcs.ISAAC.2021.26},
  annote =	{Keywords: interval edge coloring, biregular graphs, coloring algorithm}
}
  • Refine by Author
  • 1 Małafiejska, Anna
  • 1 Małafiejski, Michał
  • 1 Ocetkiewicz, Krzysztof M.
  • 1 Pastuszak, Krzysztof

  • Refine by Classification

  • Refine by Keyword
  • 1 biregular graphs
  • 1 coloring algorithm
  • 1 interval edge coloring

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact