Search

Let $box(G)$ be the boxicity of a graph $G$, $G[H_1,H_2,\ldots, H_n]$ be the $G$-generalized join graph of $n$-pairwise disjoint graphs $H_1,H_2,\ldots, H_n$, $G^d_k$ be a circular clique graph (where $k\geq 2d$) and $\Gamma(R)$ be the zero-divisor graph of a commutative ring $R$. In this paper, we prove that $\chi(G^d_k)\geq box(G^d_k)$, for all $k$ and $d$ with $k\geq 2d$. This generalizes the results proved in \cite{Aki}. Also we obtain that $box(G[H_1,H_2,\ldots,H_n])\leq \mathop\sum\limits_{i=1}^nbox(H_i)$. As a consequence of this result, we obtain a bound for boxicity of zero-divisor graph of a finite commutative ring with unity. In particular, if $R$ is a finite commutative non-zero reduced ring with unity, then $\chi(\Gamma(R))\leq box(\Gamma(R))\leq 2^{\chi(\Gamma(R))}-2$. where $\chi(\Gamma(R))$ is the chromatic number of $\Gamma(R)$. Moreover, we show that if $N= \prod\limits_{i=1}^{a}p_i^{2n_i} \prod\limits_{j=1}^{b}q_j^{2m_j+1}$ is a composite number, where $p_i$'s and $q_j$'s are distinct prime numbers, then $box(\Gamma(\mathbb{Z}_N))\leq \big(\mathop\prod\limits_{i=1}^{a}(2n_i+1)\mathop\prod\limits_{j=1}^{b}(2m_j+2)\big)-\big(\mathop\prod\limits_{i=1}^{a}(n_i+1)\mathop\prod\limits_{j=1}^{b}(m_j+1)\big)-1$, where $\mathbb{Z}_N$ is the ring of integers modulo $N$. Further, we prove that, $box(\Gamma(\mathbb{Z}_N))=1$ if and only if either $N=p^n$ for some prime number $p$ and some positive integer $n\geq 2$ or $N=2p$ for some odd prime number $p$.

The zero-divisor graph of a finite commutative ring with unity is the graph whose vertex set is the set of zero-divisors in the ring, with $a$ and $b$ adjacent if $ab=0$. We show that the class of zero-divisor graphs is universal, in the sense that every finite graph is isomorphic to an induced subgraph of a zero-divisor graph. This remains true for various restricted classes of rings, including boolean rings, products of fields, and local rings. But in more restricted classes, the zero-divisor graphs do not form a universal family. For example, the zero-divisor graph of a local ring whose maximal ideal is principal is a threshold graph; and every threshold graph is embeddable in the zero-divisor graph of such a ring. More generally, we give necessary and sufficient conditions on a non-local ring for which its zero-divisor graph to be a threshold graph. In addition, we show that there is a countable local ring whose zero-divisor graph embeds the Rado graph, and hence every finite or countable graph, as induced subgraph. Finally, we consider embeddings in related graphs such as the $2$-dimensional dot product graph.

The boxicity of a graph $G$, denoted by $box(G)$, is the least positive integer $\ell$ such that $G$ can be isomorphic to the intersection graph of a family of boxes in Euclidean $\ell$-space, where box in an Euclidean $\ell$-space is the Cartesian product of $\ell$ closed intervals on the real line. Let $k$ and $d$ be two positive integers with $k\geq 2d$. The circulant graph $G_k^d$ is the graph with vertices set $V(G_k^d)=\{a_0, a_1,\ldots, a_{k-1}\}$ and edge set $E(G_k^d)=\{a_i a_j | \ d\leq |i-j|\leq k-d\}$. Denote $\chi(G)$ the chromatic number of a graph $G$. In \cite{Aki} Akira Kamibeppu proved that $box(G_k^d)\leq \chi(G_k^d)$ for some class of circulant graph $G_k^d$ and raised the question that the same result holds for all circulant graph. In this short note, we prove that $box(G_k^d)\leq \chi(G_k^d)$, for all $k$ and $d$ with $k\geq 2d$. This include all circulant graph $G_k^d$. Our proof is very simple and short. This answer the above question., Comment: Improve the paper

Let R be a commutative ring with unity (not necessarily finite). The ring R consider as a simple graph whose vertices are the elements of R with two distinct vertices x and y are adjacent if xy=0 in R, where 0 is the zero element of R. In 1988 [8], Beck raised the conjecture that the chromatic number and clique number are same in a graph associated to any commutative ring with unity. In 1993 [2], Anderson and Naseer disproved the conjecture by giving a counter example of the conjecture (Note that, till date this is a only one counter example). In this paper, we find the clique number and bounds for chromatic number of a graph associated to any finite product of commutative rings with unity in terms of its factors (In particular, if R is finite which is not a local ring, we obtain the clique number and bounds for chromatic number of a graph associated to R in terms of its local rings). As a consequence of our results, we construct infinitely many counter examples of the above conjecture. Also, some of the main results, proved by Beck in 1988 [8] and Anderson and Naseer in 1993 [2] are consequences of our results.