Source author record

Ali Taherkhani

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

5works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

A Catlin-type Theorem for Graph Partitioning Avoiding Prescribed Subgraphs

As an extension of the Brooks theorem, Catlin in 1979 showed that if $H$ is neither an odd cycle nor a complete graph with maximum degree $Δ(H)$ , then $H$ has a vertex $Δ(H)$ -coloring such that one of the color classes is a maximum independent set. Let $G$ be a connected graph of order at least $2$ . A $G$ -free $k$ -coloring of a graph $H$ is a partition of the vertex set of $H$ into $V_1,\ldots,V_k$ such that $H[V_i]$ , the subgraph induced on $V_i$ , does not contain any subgraph isomorphic to $G$ . As a generalization of Catlin's theorem we show that a graph $H$ has a $G$ -free $\lceil{Δ(H)\over δ(G)}\rceil$ -coloring for which one of the color classes is a maximum $G$ -free subset of $V(H)$ if $H$ satisfies the following conditions; (1) $H$ is not isomorphic to $G$ if $G$ is regular, (2) $H$ is not isomorphic to $K_{kδ(G)+1}$ if $G \simeq K_{δ(G)+1}$ , and (3) $H$ is not an odd cycle if $G$ is isomorphic to $K_2$ . Indeed, we show even more, by proving that if $G_1,\ldots,G_k$ are connected graphs with minimum degrees $d_1,\ldots,d_k$ , respectively, and $Δ(H)=\sum_{i=1}^{k}d_k$ , then there is a partition of vertices of $H$ to $V_1,\ldots,V_k$ such that each $H[V_i]$ is $G_i$ -free and moreover one of $V_i$ s can be chosen in a way that $H[V_i]$ is a maximum $G_i$ -free subset of $V(H)$ except either $k=1$ and $H$ is isomorphic to $G_1$ , each $G_i$ is isomorphic to $K_{d_i+1}$ and $H$ is not isomorphic to $K_{Δ(H)+1}$ , or each $G_i$ is isomorphic to $K_{2}$ and $H$ is not an odd cycle.

preprint2016arXiv

Circular chromatic number of induced subgraphs of Kneser graphs

Investigating the equality of the chromatic number and the circular chromatic number of graphs has been an active stream of research for last decades. In this regard, Habolhassan and Zhu [Circular chromatic number of Kneser graphs, Journal of Combinatorial Theory Series B, 2003] proved that if $n$ is sufficiently large with respect to $k$ , then the Schrijver graph ${\rm SG}(n,k)$ has the same chromatic and circular chromatic number. Later, Meunier [A topological lower bound for the circular chromatic number of Schrijver graphs, Journal of Graph Theory, 2005] and independently, Simonyi and Tardos [ Local chromatic number, Ky Fan's theorem and circular colorings, Combinatorica, 2006] proved that $χ({\rm SG}(n,k))=χ_c({\rm SG}(n,k))$ if $n$ is even. In this paper, we study the circular chromatic number of induced subgraphs of Kneser graphs. In this regard, we shall first generalize the preceding result to $s$ -stable Kneser graphs. Furthermore, as a generalization of Hajiabolhassan and Zhu's result, we prove that if $n$ is large enough with respect to $k$ , then any sufficiently large induced subgraph of the Kneser graph ${\rm KG}(n,k)$ has the same chromatic number and circular chromatic number.

preprint2016arXiv

On the Spectra of Symmetric Cylindrical Constructs

In this article, following [A.~Daneshgar, M.~Hejrati, M.~Madani, {\it On cylindrical graph construction and its applications}, EJC, 23(1) p1.29, 45, 2016] we study the spectra of symmetric cylindrical constructs, generalizing some well-known results on the spectra of a variety of graph products, graph subdivisions by V.~B.~Mnuhin (1980) and the spectra of GI-graphs (see [M.~Conder, T.~Pisanski, and A.~{Ž}itnik, {\it GI-graphs: a new class of graphs with many symmetries}, 40, 209--231 (2014)] and references therein). In particular, we show that for bsymmetric cylinders with no internal vertex the spectra is actually equal to the eigenvalues of a perturbation of the base, and using this, we study the spectra of sparsifications of complete graphs by tree-cylinders. We also, show that a specific version of this construction gives rise to a class of highly symmetric graphs as a generalization of Petersen and Coxeter graphs.

preprint2014arXiv

r-Dynamic Chromatic Number of Graphs

An $r$ -dynamic $k$ -coloring of a graph $G$ is a proper vertex $k$ -coloring such that the neighbors of any vertex $v$ receive at least $\min\{r,{\rm deg}(v)\}$ different colors. The $r$ -dynamic chromatic number of $G$ , $χ_r(G)$ , is defined as the smallest $k$ such that $G$ admits an $r$ -dynamic $k$ -coloring. In this paper we introduce an upper bound for $χ_r(G)$ in terms of $r$ , chromatic number, maximum degree and minimum degree. In 2001, Montgomery \cite{MR2702379} conjectured that, for a $d$ -regular graph $G$ , $χ_2(G)-χ(G)\leq 2$ . In this regard, for a $d$ -regular graph $G$ , we present two upper bounds for $χ_2(G)-χ(G)$ , one of them, $\lceil 5.437\log d+2.721\rceil$ , is an improvement of the bound $14.06\log d +1$ , proved by Alishahi (2011) \cite{MR2746973}. Also, we give an upper bound for $χ_2(G)$ in terms of chromatic number, maximum degree and minimum degree.

preprint2011arXiv

On Coloring Properties of Graph Powers

This paper studies some coloring properties of graph powers. We show that $χ_c(G^{^{\frac{2r+1}{2s+1}}})=\frac{(2s+1)χ_c(G)}{(s-r)χ_c(G)+2r+1}$ provided that $χ_c(G^{^{\frac{2r+1}{2s+1}}})< 4$ . As a consequence, one can see that if ${2r+1 \over 2s+1} \leq {χ_c(G) \over 3(χ_c(G)-2)}$ , then $χ_c(G^{^{\frac{2r+1}{2s+1}}})=\frac{(2s+1)χ_c(G)}{(s-r)χ_c(G)+2r+1}$ . In particular, $χ_c(K_{3n+1}^{^{1\over3}})={9n+3\over 3n+2}$ and $K_{3n+1}^{^{1\over3}}$ has no subgraph with circular chromatic number equal to ${6n+1\over 2n+1}$ . This provides a negative answer to a question asked in [Xuding Zhu, Circular chromatic number: a survey, Discrete Math., 229(1-3):371--410, 2001]. Also, we present an upper bound for the fractional chromatic number of subdivision graphs. Precisely, we show that $χ_f(G^{^{\frac{1}{2s+1}}})\leq \frac{(2s+1)χ_f(G)}{sχ_f(G)+1}$ . Finally, we investigate the $n$ th multichromatic number of subdivision graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.