We study the problem of online Coloring co-interval graphs. In this problem, a set of intervals on the real line is presented to the algorithm, one at a time, and upon receiving each interval I, the algorithm must assign I a color different from the colors of all previously presented intervals not intersecting I. The objective is to use as few colors as possible. It is known that the competitive ratio of the simple FIRST-FIT algorithm on the class of co-interval graphs is at most 2. We show that for the class of unit co-interval graphs, where all intervals have equal length, the 2-bound on the competitive ratio of FIRST-FIT is tight. On the other hand, we show that no deterministic online algorithm for Coloring unit co-interval graphs can be better than 3/2-competitive. We then study the effect of randomization on our problem and show a lower bound of 4/3 on the competitive ratio of any randomized algorithm for the unit co-interval Coloring problem. We also prove that for the class of general co-interval graphs, no randomized algorithm has a competitive ratio better than 3/2.

A rapidly developing field of science and technology is nanobiotechnology. Nanotube, nanostar and polyomino chain are critical and widespread molecular structures extensively used in the domains of pharmaceuticals, chemical engineering, and medical science. Additionally, these structures serve as the foundational building blocks for other, more intricate chemical molecular structures. In this paper, certain chemical structures like nanostar dendrimer, oxide network, silicate network, boron nanosheet and polyomino chains have been acyclically colored using the concept of vertex cut and matching. Also, we determine the acyclic Coloring parameters for the networks under consideration and find a relation between them.

For a graph $G(V,E)$ which is undirected, simple, and finite, we denote by $|V|$ and $|E|$ the cardinality of the vertex set $V$ and the edge set $E$ of $G$, respectively. A \textit{graceful labeling} $f$ for the graph $G$ is an injective function ${f}:V\rightarrow \{0,1,2,..., |E|\}$ such that $\{|f(u)-f(v)|:uv\in E\}=\{1,2,...,|E|\}$. A graph that has a graceful-labeling is called \textit{graceful} graph. A vertex (resp. edge) Coloring is an assignment of color (positive integer) to every vertex (resp. edge) of $G$ such that any two adjacent vertices (resp. edges) have different colors. A \textit{graceful Coloring} of $G$ is a vertex Coloring $c: V\rightarrow \{1,2,\ldots, k\},$ for some positive integer $k$, which induces edge Coloring $|c(u)-c(v)|$, $uv\in E$. If $c$ also satisfies additional property that every induced edge color is odd, then the Coloring $c$ is called an \textit{odd-graceful Coloring} of $G$. If an odd-graceful Coloring $c$ exists for $G$, then the smallest number $k$ which maintains $c$ as an odd-graceful Coloring, is called \textit{odd-graceful chromatic number} for $G$. In the latter case we will denote the odd-graceful chromatic number of $G$ as $\mathcal{X}_{og}(G)=k$. Otherwise, if $G$ does not admit odd-graceful Coloring, we will denote its odd-graceful chromatic number as $\mathcal{X}_{og}(G)=\infty$. In this paper, we derived some facts of odd-graceful Coloring and determined odd-graceful chromatic numbers of some basic graphs.

Please click on PDF to view the abstract.

Let G = (V (G), E(G)) be a simple, finite and undirected graph of order n. A k-vertex weighting of a graph G is a mapping w: V (G) → {1, . . ., k}. A k-vertex weighting induces an edge labeling fw: E(G) → N such that fw(uv) = w(u) + w(v). Such a labeling is called an edge-Coloring k-vertex weighting if fw(e) ̸ = fw(e′ ) for any two adjacent edges e and e′ . Denote by μ ′ (G) the minimum k for G to admit an edge-Coloring k-vertex weighting. In this paper, we determine μ ′ (G) for some classes of graphs.

Web services as independent software components are published on the Internet by service providers and services are then called by users’ request. However, in many cases, no service alone can be found in the service repository that could satisfy the applicant satisfaction. Service composition provides new components by using an interactive model to accelerate the programs. Prior to service composition, the most important issue in finding suitable candidate services samples is their compliance with non-functional requirements. Thus, designing an efficient way to combine a chain of connected services is important. Recently, numerous studies have been done to reduce the search time in finding a service composition. However, many of these methods to examine and investigate all Web services in a Web repository require a long time, which occupy the user's time significantly. This paper provides an approach for automatic quality-aware service composition as well as the users’ preferences in achieving the optimum composition results. For this purpose, modified graph Coloring method to filter the data before compositions in large-scale data is used which decreases selected services set. The application of KPL algorithm in this study provided some proper solutions to the user so that these solutions can be used instead of the best composition if necessary. Therefore, the results derived from the analysis of the proposed method, indicates a good optimization in runtime and memory consumption. The evaluation results show that the proposed method in memory consumption and runtime has improved by about 20%.