Narrow Results

Let $S\subseteq V$. A vertex $v\in V$ is a dominator of $S$ if $v$ dominates every vertex in $S$ and $v$ is said to be an anti-dominator of $S$ if $v$ dominates none of the vertices of $S$. Let ${𝒞}=(V_1,V_2,\dots ,V_k)$ be a coloring of $G$ and let $v\in V(G)$. A color class $V_i$ is called a dom-color class or an anti-dom-color class of the vertex $v$ according as $v$ is a dominator of $V_i$ or an anti-dominator of $V_i$. The coloring ${𝒞}$ is called a global dominator coloring of $G$ if every vertex of $G$ has a dom-color class and an anti-dom-color class in ${𝒞}$. The minimum number of colors required for a global dominator coloring of $G$ is called the global dominator chromatic number and is denoted by ${\chi }_{\mathrm{\text{gd}}}(G)$. This parameter was introduced in [I. S. Hamid and M. Rajeswari, Global dominator coloring of graphs, Discuss. Math. Graph Theory 39 (2019) 325–339]. This paper further extends the study by obtaining the value of ${\chi }_{\mathrm{\text{gd}}}$ for unicyclic graphs.

The lucky edge coloring of graph $G$ is a proper edge coloring which is induced by a vertex coloring such that each edge is labeled by the sum of its vertices. The least integer $k$ for which $G$ has a lucky edge coloring in the set $\{1,2,\dots ,k\}$ is called lucky number, denoted by $\eta (G)$. The lucky numbers were already calculated for a large number of graphs, but not yet for trees. In this paper, we provide the characterization of lucky edge coloring and calculate the lucky number for graphs which can be regarded as complete $m$-ary trees.

In [1], Borodin et al. figured out a gap of [5], and gave a new proof with the similar technique. The purpose of this note is to fix the gap of [5] by slightly revising the definition of special faces, and adding a few lines of explanation in the original proofs of [5] (new added text are all in italic type).

We look at the problem of coloring locally specially constructed spanners of unit disk graphs. First we present a local approximation algorithm for the vertex coloring problem in Unit Disk Graphs (UDGs) which uses at most four times as many colors as an optimal solution requires. Next we look at the colorability of spanners of UDGs. In particular we present a local algorithm for constructing a 4-colorable spanner of a unit disk graph. The output consists of the spanner and the 4-coloring. The computed spanner also has the properties that it is planar, the degree of a vertex in the spanner is at most 5 and the angles between two edges are at least π/3. By enlarging the locality distance (i.e. the size of the neighborhood which a vertex has to explore in order to compute its color) we can ensure the total weight of the spanner to be arbitrarily close to the weight of a minimum spanning tree.

We prove that a local algorithm cannot compute a bipartite spanner of a unit disk graph and therefore our algorithm needs at most one color more than any local algorithm for the task requires. Moreover, we prove that there is no local algorithm for 3-coloring UDGs or spanners of UDGs, even if the 3-colorability of the graph (or the spanner respectively) is guaranteed in advance.

In this paper, we associate the graph Γ_I(N) to an ideal I of a near-ring N. We exhibit some properties and structure of Γ_I(N). For a commutative ring R, Beck conjectured that both chromatic number and clique number of the zero-divisor graph Γ(R) of R are equal. We prove that Beck's conjecture is true for Γ_I(N). Moreover, we characterize all right permutable near-rings N for which the graph Γ_I(N) is finitely colorable.

In a graph $G=(V,E)$, a vertex $v$ dominates a vertex $w$ if either $v=w$ or $v$ is adjacent to $w$. A subset of vertex set $V$ that dominates all the vertices of $G$ is called a dominating set of graph $G$. The minimum cardinality of a dominating set of $G$ is called the domination number of $G$ and is denoted by $\gamma (G)$. A proper coloring of a graph $G$ is an assignment of colors to the vertices of $G$ such that any two adjacent vertices get different colors. The minimum number of colors required for a proper coloring of $G$ is called the chromatic number of $G$ and is denoted by $\chi (G)$. A dominator coloring of a graph $G$ is a proper coloring of the vertices of $G$ such that every vertex dominates all the vertices of at least one color class. The minimum number of colors required for a dominator coloring of $G$ is called the dominator chromatic number of $G$ and is denoted by ${\chi }_d(G)$. In this paper, we study the dominator chromatic number for the proper interval graphs and block graphs. We show that every proper interval graph $G$ satisfies $\chi (G)+\gamma (G)-2\le {\chi }_d(G)\le \chi (G)+\gamma (G)$, and these bounds are sharp. For a block graph $G$, where one of the end block is of maximum size, we show that $\chi (G)+\gamma (G)-1\le {\chi }_d(G)\le \chi (G)+\gamma (G)$. We also characterize the block graphs with an end block of maximum size and attaining the lower bound.

In this paper, we present the class of $\delta \mathrm{\text{EFL}}$ graphs and then prove a generalized statement of the Erdős–Faber–Lovász conjecture for this graph class. Then, the Erdős–Faber–Lovász conjecture follows for every graph in this class.

Sampathkumar [F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969)] defined the coloring of a digraph $D=(V,A)$ as a coloring of its vertices by the following rule: Let $uv$ be an arc in $D$. If the tail $u$ is colored first, then the head $v$ should receive a color different from that of $u$. But, if $v$ is colored first, then $u$ may or may not receive the color of $v$. The dichromatic number${\chi }_d(D)$ of a digraph $D$ is the minimum number of colors needed for coloring of a digraph $D$. In this paper, we obtain some results on uniquely colorable digraphs and Nordhaus–Gaddum type results for digraphs.

In this paper, we introduce and study a new coloring problem of graphs called the double total dominator coloring. A double total dominator coloring of a graph $G$ with minimum degree at least 2 is a proper vertex coloring of $G$ such that each vertex has to dominate at least two color classes. The minimum number of colors among all double total dominator coloring of $G$ is called the double total dominator chromatic number, denoted by ${\chi }_{dd}^t(G)$. Therefore, we establish the close relationship between the double total dominator chromatic number ${\chi }_{dd}^t(G)$ and the double total domination number ${\gamma }_{\times 2,t}(G)$. We prove the NP-completeness of the problem. We also examine the effects on ${\chi }_{dd}^t(G)$ when $G$ is modified by some operations. Finally, we discuss the ${\chi }_{dd}^t(G)$ number of square of trees by giving some bounds.

A connected graph $G$ is double-critical if the chromatic number of $G-x-y$ is two less than that of $G$ whenever $x$ and $y$ are two adjacent vertices of $G$. The double-critical graph conjecture states that the complete graphs are the only double-critical graphs. We give a proof of this conjecture for any double-critical graph that contains at least one universal vertex. Using this result we prove the conjecture for all double-critical graphs.