Online Rainbow Coloring in Graphs

EasyChair Preprint 14909

Abstract

Rainbow coloring is a special case of edge coloring, where there must be at least one path between every distinct pair of vertices that consists of different color edges. Here, we may use the same color for the adjacent edges of a graph representing two different paths from a single vertex. In \textit{online rainbow coloring}, we have no prior knowledge about the vertices and edges of the graph, in fact, the edges are available one by one. We have to color an edge as soon as it arrives and before the arrival of the next edge. We can not revoke the coloring decision once it is made. According to our knowledge, there is no study of online rainbow coloring for graphs. In this paper, we make a first attempt to propose an online algorithm named \textit{Least Recently Used Color(LRUC)} for \textit{ online rainbow coloring}. We analyze the performance of \textit{LRUC} through competitive analysis. We show that \textit{LRUC} is optimal for line graph, tree and star graph. For $1$-cyclic graph, \textit{LRUC} is shown to be $(2-\frac{2}{n})$)-competitive, where $n \geq 4$. We obtain the competitive ratios of $\frac{n-1}{3}$ and $n-1$ for wheel and complete graphs respectively, where $n$ is the number of vertices.

Keyphrases: Online Rainbow Coloring, competitive analysis, graph coloring, online algorithm, rainbow coloring

@booklet{EasyChair:14909,
  author    = {Debasis Dwibedy and Rakesh Mohanty and Arun Khamari},
  title     = {Online Rainbow Coloring in Graphs},
  howpublished = {EasyChair Preprint 14909},
  year      = {EasyChair, 2024}}