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.

In a graph G=(V, E), an independent set I(G) is a subset of the vertices of G such that no two vertices in I(G) are adjacent. Any maximum independent set of a graph is called a diagonal of the graph. Let c be a proper (r+1)-Coloring of an r-regular graph G. A vertex v in G is said to be rainbow with respect to c if every color appears in the closed neighborhood N[v]=N(v)∪ {v}. Given a diagonal I of G, the Coloring c is said to be silver with respect to I if every v∈ I is rainbow with respect to c. G is called silver if it admits a silver Coloring with respect to some diagonal. In [1], the authors introduced silver Coloring and the following question is raised “ Find classes of r-regular graphs G, that G is a silver graph". This paper is aimed toward study this question for the generalized Petersen graphs. In this paper we show that, if n≡ 0 (mod4) and k is odd, then P(n, k) is a totally silver graph. Also, for every natural number n, the existence of silver Coloring for generalized Petersen graphs P(n, 1), P(n, 2) except for n=5, this is well-known petersen graph, P(n, 3) except for n=10, 14 and 26. Also, for any k>2, P(2k+1, k), and for any k>3, P(3k+1, k), and for any k>3, k ≠ 5, 9 P(3k-1, k) are silver graphs.

The injective chromatic number $\chi_i(G)$ of a graph $G$ is the smallest number of colors required to color the vertices of $G$ such that any two vertices with a common neighbor are assigned distinct colors. The Mycielskian or Mycielski graph $\mu(G)$ of a graph $G$, introduced by Jan Mycielski in 1955 has the property that, these graphs have large chromatic number with small clique number. The generalized Mycielskian $\mu_m(G),m>0$ (also known as cones over graphs) are the natural generalizations of the Mycielski graphs. In this paper, sharp bounds are obtained for the injective chromatic number of generalized Mycielskian of any graph $G$. Further, the injective chromatic number of generalized Mycielskian of some special classes of graphs such as paths, cycles, complete graphs, and complete bipartite graphs are obtained.