\noindent A fall $k$-coloring of a graph $G$ is a proper $k$-coloring of $G$ such that each vertex of $G$ sees all $k$ colors on its closed neighborhood. In this note, we characterize all fall colorings of Kneser graphs of type $KG(n,2)$ for $n\geq2$ and study some fall colorings of $KG(n,m)$ in some special cases and introduce some bounds for fall colorings of Kneser graphs.\\ \noindent {Keywords:}\ { Fall coloring, graph homomorphism, Kneser graph.}\\ {Subject classification: 05C}
0909.2772.tex
%88-3-25
% Lower-case    a b c d e f g h i j k l m n o p q r s t u v w x y z
% Digits        0 1 2 3 4 5 6 7 8 9
% Exclamation   !           Double quote "          Hash (number) #
% Dollar        $           Percent      %          Ampersand     &
% Acute accent  '           Left paren   (          Right paren   )
% Asterisk      *           Plus         +          Comma         ,
% Minus         -           Point        .          Solidus       /
% Colon         :           Semicolon    ;          Less than     <
% Equals        =           Greater than >          Question mark ?
% At            @           Left bracket [          Backslash     \
% Right bracket ]           Circumflex   ^          Underscore    _
% Grave accent  `           Left brace   {          Vertical bar  |
% Right brace   }           Tilde        ~
%%draft1.tex  9 July 2007, Uses EM-TEX/LATEX209 or latest %%
%\documentstyle[11pt]{article}
%%- Set up for A4 paper %%
\documentclass[11pt]{article}
\usepackage{amssymb}
%\usepackage{latexsym,amsmath}
\oddsidemargin   = 0 cm \evensidemargin  = 0 cm \textwidth  = 14
cm \textheight = 22 cm \headheight=0cm \topskip=0cm \topmargin=0cm
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{precor}{{\bf Corollary}}
\renewcommand{\theprecor}
{{\arabic{precor}}}
\newenvironment{cor}{\begin{precor}{\hspace{-0.5
               em}{\bf.\ }}}{\end{precor}}
%
\newtheorem{precon}{{\bf Conjecture}}
\renewcommand{\theprecon}
{{\arabic{precon}}}
\newenvironment{con}{\begin{precon}{\hspace{-0.5
               em}{\bf.\ }}}{\end{precon}}
%
%
\newtheorem{prealphcon}{{\bf Conjecture}}
\renewcommand{\theprealphcon}
{{\Alph{prealphcon}}}
\newenvironment{alphcon}{\begin{prealphcon}{\hspace{-0.5
               em}{\bf.\ }}}{\end{prealphcon}}
%
\newtheorem{predefin}{{\bf Definition}}
\renewcommand{\thepredefin}{{\arabic{predefin}}}
\newenvironment{defin}[1]{\begin{predefin}{\hspace{-0.5
                   em}{\bf.\ }}{\rm #1}\hfill{$\spadesuit$}}{\end{predefin}}
%
\newtheorem{preexm}{{\bf Example}}
\renewcommand{\thepreexm}
{{\arabic{preexm}}}
\newenvironment{exm}[1]{\begin{preexm}{\hspace{-0.5
                  em}{\bf.\ }}{\rm #1}\hfill{$\clubsuit$}}{\end{preexm}}

%
%
\newtheorem{preappl}{{\bf Application}}
\renewcommand{\thepreappl}
{{\arabic{preappl}}}
\newenvironment{appl}[1]{\begin{preappl}{\hspace{-0.5
                  em}{\bf.\ }}{\rm #1}\hfill{$\blacklozenge$}}{\end{preappl}}


%
\newtheorem{prelem}{{\bf Lemma}}
\renewcommand{\theprelem}
{{\arabic{prelem}}}
\newenvironment{lem}{\begin{prelem}{\hspace{-0.5
               em}{\bf.\ }}}{\end{prelem}}
%
\newtheorem{preproof}{{\bf Proof.\ }}
\renewcommand{\thepreproof}{}
\newenvironment{proof}[1]{\begin{preproof}{\rm
               #1}\hfill{$\blacksquare$}}{\end{preproof}}
%
\newtheorem{pretheorem}{{\bf Theorem}}
\renewcommand{\thepretheorem}
{{\arabic{pretheorem}}}
\newenvironment{theorem}{\begin{pretheorem}{\hspace{-0.5
               em}{\bf.\ }}}{\end{pretheorem}}
%
\newtheorem{prealphtheorem}{{\bf Theorem}}
\renewcommand{\theprealphtheorem}
{{\Alph{prealphtheorem}}}
\newenvironment{alphtheorem}{\begin{prealphtheorem}{\hspace{-0.5
               em}{\bf.\ }}}{\end{prealphtheorem}}
%

\newtheorem{prealphlem}{{\bf Lemma}}
\renewcommand{\theprealphlem}
{{\Alph{prealphlem}}}
\newenvironment{alphlem}{\begin{prealphlem}{\hspace{-0.5
               em}{\bf.\ }}}{\end{prealphlem}}


%
\newtheorem{prepro}{{\bf Proposition}}
\renewcommand{\theprepro}
{{\arabic{prepro}}}
\newenvironment{pro}{\begin{prepro}{\hspace{-0.5
               em}{\bf.\ }}}{\end{prepro}}
%
\newtheorem{preprb}{{\bf Problem}}
\renewcommand{\thepreprb}
{{\arabic{preprb}}}
\newenvironment{prb}{\begin{preprb}{\hspace{-0.5
               em}{\bf.\ }}}{\end{preprb}}
%
\newtheorem{prerem}{{\bf Remark}}
\renewcommand{\theprerem}
{{\arabic{prerem}}}
\newenvironment{rem}{\begin{prerem}{\hspace{-0.5
               em}{\bf.\ }}}{\end{prerem}}
%
\newtheorem{preapp}{{\bf Application}}
\renewcommand{\thepreapp}
{{\arabic{preapp}}}
\newenvironment{app}[1]{\begin{preapp}{\hspace{-0.5
                  em}{\bf.\ }}{\rm #1}\hfill{$\bigstar$}}{\end{preapp}}
%
%
\newtheorem{prequ}{{\bf Question}}
\renewcommand{\theprequ}
{{\arabic{prequ}}}
\newenvironment{qu}{\begin{prequ}{\hspace{-0.5
               em}{\bf.\ }}}{\end{prequ}}
%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\def\ra{\ \rightarrow\ }
\def\lra{\ \longrightarrow\ }
\def\conct[#1,#2]{\mbox {${#1} \leftrightarrow {#2}$}}
\def\dconct[#1,#2]{\mbox {${#1} \rightarrow {#2}$}}
\def\deg[#1,#2]{\mbox {$d_{_{#1}}(#2)$}}
\def\mindeg[#1]{\mbox {$\delta_{_{#1}}$}}
\def\maxdeg[#1]{\mbox {$\Delta_{_{#1}}$}}
\def\outdeg[#1,#2]{\mbox {$d_{_{#1}}^{^+}(#2)$}}
\def\minoutdeg[#1]{\mbox {$\delta_{_{#1}}^{^+}$}}
\def\maxoutdeg[#1]{\mbox {$\Delta_{_{#1}}^{^+}$}}
\def\indeg[#1,#2]{\mbox {$d_{_{#1}}^{^-}(#2)$}}
\def\minindeg[#1]{\mbox {$\delta_{_{#1}}^{^-}$}}
\def\maxindeg[#1]{\mbox {$\Delta_{_{#1}}^{^-}$}}
\def\isdef{\mbox {$\ \stackrel{\rm def}{=} \ $}}
\def\dre[#1,#2,#3]{\mbox {${\cal E}^{^{#3}}(#1,#2)$}}
\def\var[#1,#2]{\mbox {${\rm Var}_{_{#1}}(#2)$}}
\def\ls[#1]{\mbox {$\xi^{^{#1}}$}}
\def\hom[#1,#2]{\mbox {${\rm Hom}({#1},{#2})$}}
\def\onvhom[#1,#2]{\mbox {${\rm Hom^{v}}(#1,#2)$}}
\def\onehom[#1,#2]{\mbox {${\rm Hom^{e}}(#1,#2)$}}
\def\core[#1]{\mbox {$#1^{^{\bullet}}$}}
\def\cay[#1,#2]{\mbox {${\rm Cay}({#1},{#2})$}}
\def\sch[#1,#2,#3]{\mbox {${\rm Sch}({#1},{#2},{#3})$}}
\def\cays[#1,#2]{\mbox {${\rm Cay_{s}}({#1},{#2})$}}
\def\dirc[#1]{\mbox {$\stackrel{\rightarrow}{C}_{_{#1}}$}}
\def\cycl[#1]{\mbox {${\bf Z}_{_{#1}}$}}
\def\edg{\mbox {$\stackrel{\rightarrow}{E}$}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%\setcounter{page}{183}
%{\footnotesize AAA {\bf ?} (200?) ?--?}\\
%\maketitle

\begin{center}
{\Large \bf On Fall Colorings of Kneser Graphs}\\
\vspace{0.3 cm}
{\bf Saeed Shaebani}\\
{\it Department of Mathematical Sciences}\\
{\it Institute for Advanced Studies in Basic Sciences {\rm (}IASBS{\rm )}}\\
{\it P.O. Box {\rm 45195-1159}, Zanjan, Iran}\\
{\tt s\_shaebani@iasbs.ac.ir}\\ \ \\
\end{center}
\begin{abstract}
\noindent A fall $k$-coloring of a graph $G$ is a proper
$k$-coloring of $G$ such that each vertex of $G$ sees all $k$
colors on its closed neighborhood. In this note, we characterize
all fall colorings of Kneser graphs of type $KG(n,2)$ for $n\geq2$
and study some fall colorings of $KG(n,m)$ in some special
cases and introduce some bounds for fall colorings of Kneser graphs.\\

\noindent {\bf Keywords:}\ {  Fall coloring, graph homomorphism, Kneser graph.}\\
{\bf Subject classification: 05C}
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
All graphs considered in this paper are finite and simple
(undirected, loopless and without multiple edges). Let $G=(V,E)$
be a graph and $k\in \mathbb{N}$ and let $[k]=\{i|\ i\in
\mathbb{N},\ 1\leq i\leq k \}$. A $k$-coloring (proper k-coloring)
of $G$ is a function $f:V\rightarrow [k]$ such that for each
$1\leq i\leq k$, $f^{-1}(i)$ is an independent set. We say that
$G$ is $k$-colorable whenever $G$ has a $k$-coloring $f$, in this
case, we denote $f^{-1}(i)$ by $V_{i}$ and call each $1\leq i\leq
k$, a color (of $f$) and each $V_{i}$, a color class (of $f$). The
minimum integer $k$ for which $G$ has a $k$-coloring, is called
the chromatic number of G and is denoted by $\chi(G)$.

Let $G$ be a graph and $f$ be a $k$-coloring of $G$ and $v$ be a
vertex of $G$. The vertex $v$ is called colorful ( or
color-dominating or $b$-dominating) if each color $1\leq i\leq k$
appears on the closed neighborhood of $v$ (\ $f(N[v])=[k]$ ). The
$k$-coloring $f$ is said to be a fall $k$-coloring (of $G$) if
each vertex of $G$ is colorful. There are graphs $G$ for which
$G$ has no fall $k$-coloring for any positive integer $k$. For
example, $C_{5}$ (a cycle with 5 vertices) and graphs with at
least one edge and one isolated vertex, have not any fall
$k$-colorings for any positive integer $k$. The notation ${\rm
Fall}(G)$ stands for the set of all positive integers $k$ for
which $G$ has a fall $k$-coloring. Whenever ${\rm
Fall}(G)\neq\emptyset$, we call $\min({\rm Fall}(G))$ and
$\max({\rm Fall}(G))$, fall chromatic number of $G$ and fall
achromatic number of $G$ and denote them by $\chi_{f}(G)$ and
$\psi_{f}(G)$, respectively. The terminology fall coloring was
firstly introduced in 2000 in \cite{dun} and has received
attention recently, see
\cite{MR2096633},\cite{MR2193924},\cite{dun},\cite{las}.

Let $G$ be a graph and $k\in \mathbb{N}$ and $f$ be a
$k$-coloring of $G$. The coloring $f$ is said to be a colorful
$k$-coloring of $G$ if each color class contains at least one
colorful vertex. The maximum integer $k$ for which $G$ has a
colorful $k$-coloring, is called the $b$-chromatic number of $G$
and is denoted by $\phi(G)$ ( or $b(G)$ or $\chi_{b}(G)$).

Let $t,v,k,\lambda$ be positive integers and $v\geq k\geq t$. A
$(S,B)=t-(v,k,\lambda)$ block design is a family $B$ of some
$k$-subsets (blocks) of a $v$-set $S$ such that every $t$-subset
of $S$ is contained in exactly $\lambda$ blocks. If $t=2$, $k=3$
and $\lambda=1$, the $(S,B)=t-(v,k,\lambda)$ block design is
sometimes called an Steiner Triple System and denoted by $STS(v)$.

\section{Fall colorings of Kneser graphs}

Suppose that $n\geq m$. Hereafter, we denote by ${[n] \choose m}$
the set of all $m$-subsets of $[n]$. The {\it Kneser graph}
$KG(n,m)$ has the vertex set ${[n] \choose m}$, in which $A \sim
B$ if and only if $A \cap B = \emptyset$. It was conjectured by
Kneser in 1955 \cite{KG}, and proved by Lov{\'a}sz in 1978
\cite{lov}, that if $n\geq 2m$, then, $\chi (KG(n,m))=n-2m+2$.
Lov{\'a}sz's proof was the beginning of using algebraic topology
in combinatorics. Colorful colorings of Kneser graphs have been
studied in \cite{haj} and \cite{jav}. In this paper we study fall
colorings of Kneser graphs.



Let $G$ and $H$ be graphs. A function $f:V(G)\rightarrow V(H)$ is
called a type-II graph homomorphism from $G$ to $H$ if $f$
satisfies the following two conditions:
\\
\\
1) $\{u,v\}\in E(G)\Rightarrow \{f(u),f(v)\}\in E(H)$.
\\
2) $\{u_{1},v_{1}\}\in E(H)\Rightarrow \forall v\in
f^{-1}(v_{1}): \exists u\in f^{-1}(u_{1})$ s.t $\{u,v\}\in E(G)$.
\\
\\
Type-II graph homomorphisms introduced by Laskar and Lyle in 2009
in \cite{las}.\ They showed that for any graph $G$, $k\in {\rm
Fall}(G)$ iff there exists a type-II graph homomorphism from $G$
to $K_{k}$. It is simple to see that if $f_{1}$ is a type-II
graph homomorphism from $G$ to $H$ and $f_{2}$ is a type-II graph
homomorphism from $H$ to $I$, then, $f_{2}of_{1}$ is a type-II
graph homomorphism from $G$ to $I$. Also, if there exists a
type-II graph homomorphism from $G$ to $H$ and $k\in {\rm
Fall}(H)$, then, $k\in {\rm Fall}(G)$.



\begin{theorem}{\label{mainthm} Let $n,m\in\mathbb{N}$ and $n>2m$ and $m\geq2$.
Then, ${\rm Fall}(KG(n,m))\subseteq {\rm Fall}(KG(n+2,m+1))$.}
\end{theorem}
\begin{proof}
{The function $f:V(KG(n+2,m+1))\rightarrow V(KG(n,m))$ which
assigns to each $A\subseteq [n+2]$ with $|A\bigcap
\{n+1,n+2\}|\leq1$, $f(A)=A\setminus\{\max A\}$ and to each
$A\subseteq [n+2]$ with $\{n+1,n+2\}\subseteq A$,
$f(A)=(A\setminus\{n+1,n+2\})\bigcup \{\max ([n]\setminus A)\}$,
is a type-II graph homomorphism from $KG(n+2,m+1)$ to $KG(n,m)$
and therefore, ${\rm Fall}(KG(n,m))\subseteq {\rm
Fall}(KG(n+2,m+1))$.}
\end{proof}

\begin{cor}{ Let $a,b\in\mathbb{N}\bigcup\{0\}$ and $a>2b$. Also, for each $i\in \mathbb{N}\setminus\{1\}$, let $F_{i}:=Fall(KG(2i+a,i+b))$.
Then,
$F_{2}\subseteq F_{3}\subseteq F_{4}\subseteq ...\subseteq
F_{n}\subseteq F_{n+1}\subseteq ...$ .}
\end{cor}

Now we investigate fall colorings of Kneser graphs of type
$KG(n,2)$. Hereafter, we suppose that the vertex set of $K_{n}$
is $[n]$. For $n\geq2$, $KG(n,2)$ is exactly the complement graph
of the line graph of $K_{n}$. Therefore, one can think of
$KG(n,2)$ as the graph whose vertex set is $E(K_{n})$ in which
two elements of $E(K_{n})$ are adjacent in $KG(n,2)$ iff they
have not any common vertices in $K_{n}$.

\begin{theorem}{\label{thm1} For each natural number
$n\geq2$, we have
\\
\\
${\rm Fall}(KG(n,2))=\left\{\begin{array}{ll}
  \{1\} & n=2\ {\rm or}\ 3 \\
  \{2\} & n=4\\
  \{\frac{n(n-1)}{6}\}& n\geq5,\ n=1\ {\rm or}\ 3\ ({\rm mod}\ 6) \\
  \{\frac{(n-1)(n-2)}{6}+1\} & n\geq5,\ n=2\ {\rm or}\ 4\ ({\rm mod}\ 6) \\
  \emptyset & n\geq5,\ n=0\ {\rm or}\ 5\ ({\rm mod}\ 6)
\end{array}\right.$
}
\end{theorem}


\begin{proof}{
Obviously, ${\rm Fall}(KG(2,2))={\rm Fall}(KG(3,2))=\{1\}$. Also,
since $KG(4,2)$ is a matching, ${\rm Fall}(KG(4,2))=\{2\}$. Now
let's suppose that $n\geq5$. Let $k,n\in\mathbb{N}$, $n\geq5$,
and $f$ be a fall $k$-coloring of $KG(n,2)$. Also, let ${\cal A}$
be an arbitrary color class of $f$ and $\{a,b\}$ be an arbitrary
element of ${\cal A}$. Obviously, ${\cal A}\neq \{\ \{a,b\}\ \}$,
since, for any $c_{0}\in [n]\setminus\{a,b\}$, $\{a,c_{0}\}\notin
{\cal A}$ and $\{a,c_{0}\}$ has not any neighbors in ${\cal A}$
which contradicts the fact that $f$ is a fall $k$-coloring of
$KG(n,2)$. Therefore, there exists another vertex $\bar{x}$ in
${\cal A}$. With no loss of generality, we can assume that
$\{a,b\}\bigcap \bar{x}=\{a\}$. Hence, $\exists c\in [n]$ such
that $\bar{x}=\{a,c\}$. Again, ${\cal A}\neq \{\ \{a,b\},\{a,c\}\
\}$, otherwise, $\{b,c\}\notin {\cal A}$ and has no neighbors in
${\cal A}$, which is a contradiction. Consequently, there exists
another vertex $\bar{y}\in {\cal A}$. Now there are two cases:

Case I) $\bar{y}=\{b,c\}$. In this case, obviously ${\cal A}=\{\
\{a,b\},\{a,c\},\{b,c\}\ \}$.

Case II) $\bar{y}\neq \{b,c\}$. Therefore, in this case, $a\in
 \bar{y}$
and there exists $d\in [n]\setminus\{a,b,c\}$ such that
$\bar{y}=\{a,d\}$ and obviously, each element of ${\cal A}$
contains $a$, otherwise, there exist two adjacent vertices in
${\cal A}$, which is a contradiction. Thus, ${\cal A}\subseteq
S_{a}:= \{\ \{a,x\}\ |\ x\in [n]\setminus\{a\}\ \}$. Now, we
prove that ${\cal A}=S_{a}$. If ${\cal A}\subsetneqq S_{a}$, then
there exists $z\in [n]\setminus\{a\}$ such that $\{a,z\}\notin
{\cal A}$. Hence, $\{a,z\}$ is not in ${\cal A}$ and has no
neighbors in ${\cal A}$, which is a contradiction. Hence, ${\cal
A}=S_{a}$.

Therefore, for each color class ${\cal A}$ of $f$, either there
exist three distinct elements $a,b,c\in [n]$ such that ${\cal
A}=\{\ \{a,b\},\{b,c\},\{c,a\}\ \}$ or there exists an element
$a\in [n]$ such that ${\cal A}=S_{a}$. Hereafter, we call each
color class of type $\{\ \{a,x\}\ |\ x\in [n]\setminus\{a\}\ \}$
where $a$ is a fixed element of $[n]$, a complete star in $K_{n}$
and each color class of type $\{\ \{a,b\},\{b,c\},\{c,a\}\ \}$
where $|\{a,b,c\}|=3$, a triangle in $K_{n}$. It's easy to see
that there exists at most one element $a\in [n]$ such that
$S_{a}$ is a color class of $f$, otherwise, there exists a common
vertex in two distinct color classes, which is a contradiction.
Hence, the set of color classes of $f$, is either a partition of
edge set of $K_{n}$ into one complete star and triangles or a
partition of edges of $K_{n}$ into triangles. Consequently, the
edge set of $K_{n}$ or $K_{n-1}$ can be partitioned into
triangles. On the other hand, it is well known that the edge set
of $K_{n}$ (resp. $K_{n-1}$) can be partitioned into triangles iff
an Steiner Triple System $2-(n,3,1)$ (resp. Steiner Triple System
$2-(n-1,3,1)$) exists and this is equivalent with $n=1\ {\rm or}\
3\ ({\rm mod}\ 6)$ (resp. $n-1=1\ {\rm or}\ 3\ ({\rm mod}\ 6)$).
Therefore, if ${\rm Fall}(KG(n,2))\neq\emptyset$, then, $n=1\
{\rm or}\ 2\ {\rm or}\ 3\ {\rm or}\ 4\ ({\rm mod}\ 6)$.
Conversely, if $n=1\ {\rm or}\ 3\ ({\rm mod}\ 6)$, every
partition of edge set of $K_{n}(n\geq2)$ into triangles, is the
set of color classes of a fall $\frac{n(n-1)}{6}$-coloring of
$KG(n,2)$. Similarly, if $n-1=1\ {\rm or}\ 3\ ({\rm mod}\ 6)$
every partition of edge set of $K_{n}(n\geq2)$ into one complete
star and triangles, is the set of color classes of a fall
$(\frac{(n-1)(n-2)}{6}+1)$-coloring of $KG(n,2)$. Therefore, the
following characterization implies


$n\geq2\Rightarrow {\rm Fall}(KG(n,2))=\left\{\begin{array}{ll}
  \{1\} & n=2\ {\rm or}\ 3 \\
  \{2\} & n=4\\
  \{\frac{n(n-1)}{6}\}& n\geq5,\ n=1\ {\rm or}\ 3\ ({\rm mod}\ 6) \\
  \{\frac{(n-1)(n-2)}{6}+1\} & n\geq5,\ n=2\ {\rm or}\ 4\ ({\rm mod}\ 6) \\
  \emptyset & n\geq5,\ n=0\ {\rm or}\ 5\ ({\rm mod}\ 6)
\end{array}\right.$



}
\end{proof}


Now we study some fall colorings of other Kneser graphs in some
special cases. $KG(n,1)$ is a complete graph with $n$ vertices
and therefore, ${\rm Fall}(KG(n,1))=\{n\}$. If $m,n\in \mathbb{N}$
and $\frac{n}{2}<m\leq n$, then, $E(KG(n,m))=\emptyset$ and
therefore, ${\rm Fall}(KG(n,m))=\{1\}$. If $m,n\in \mathbb{N}$
and $n=2m$, then, $E(KG(n,m))$ is a perfect matching of $KG(n,m)$
and hence, ${\rm Fall}(KG(n,m))=\{2\}$.

Javadi and Omoomi observed that if $n,m\in\mathbb{N}$ and $1\leq
m\leq \frac{n}{2}$ and an $(S,B)= m-(n,2m-1,1)$ block design
exists, then, $T:=\{\ \{X|\ X\subseteq C,\ |X|=m\}\ |\ C\in B\ \}$
is the set of color classes of a colorful $|B|$-coloring $f$ of
$KG(n,m)$ and each vertex of $KG(n,m)$ is colorful with respect
to $f$ \cite{jav}. Indeed, they have shown that with these
conditions, ${\rm Fall}(KG(n,m))\neq\emptyset$ and $|B|\in {\rm
Fall}(KG(n,m))$.

\begin{theorem}{\label{thm2}
If $n,m\in\mathbb{N}$ and $1\leq m\leq \frac{n}{2}$ and an
$(S,B)= m-(n,2m-1,1)$ block design exists, then, $|B|\in {\rm
Fall}(KG(n,m))$.}
\end{theorem}


For $m=2$ and $n\geq5$, this shows that if an Steiner Triple
System $2-(n,3,1)$ exists or equivalently, $n=1\ {\rm or}\ 3\
({\rm mod}\ 6)$, then, $\frac{n(n-1)}{6}\in {\rm Fall}(KG(n,2))$.
 Also, we can add the following:
\begin{pro}{\label{thm3} If $m,n\in \mathbb{N}$ and $2\leq m\leq
\frac{n}{2}$ and a $(S,B)=\ (m-1)-(n,2m-3,1)$ block design
exists, then, $|B|+1\in {\rm Fall}(KG(n,m))$.}
\end{pro}
\begin{proof}{ Consider a fall $|B|$-coloring $f$ of $KG(n,m-1)$ as described
and then add $\{A|\ A\subseteq [m],\ |A|=m,\ m\in A\}$ to the set
of color classes of $f$ in order to constructing a fall
$(|B|+1)$-coloring of $KG(n,m)$.

}\end{proof}


One can see that combining the Theorem \ref{mainthm} with each of
Theorem \ref{thm1}, Theorem \ref{thm2}, and Proposition
\ref{thm3} is very fruitful.
\\

Now we introduce some bounds for $\chi_{f}(KG(n,m))$.
\\
\\
Let $S$ be a nonempty independent set in $KG(n,m)$. $S$ is called
intersecting if $\bigcap_{A\in S}A\neq\emptyset$ and
non-intersecting if $\bigcap_{A\in S}A=\emptyset$. Hilton-Milner
theorem \cite{hil} states that if $n\geq 2m$, then, the maximum
size of a non-intersecting independent set in $KG(n,m)$ is at most
$h_{n,m}:=1+{{n-1 \choose m-1}}-{{n-m-1 \choose m-1}}$. Let
$n,m,k\in \mathbb{N}$ and $n\geq 2m$ and $f$ be a fall
$k$-coloring of $KG(n,m)$ and $S$ be an intersecting color class
of $f$ and let $i\in \bigcap_{A\in S}A$. Each vertex $B$ of
$KG(n,m)$ which contains $i$, is an element of $S$, otherwise,
$B\notin S$ and $B$ has not any neighbors in $S$, contradicting
the fact that $f$ is a fall $k$-coloring of $KG(n,m)$. Also, since
$n\geq 2m$, for each $j\in [n]\setminus \{i\}$, there exists a
vertex $C$ of $KG(n,m)$ which $i\in C$ and $j\notin C$ and $C\in
S$, therefore, $\bigcap_{A\in S}A=\{i\}$ and $S=\{A|\ A\in {[n]
\choose m}\ {\rm and}\  i\in A\}$ and $|S|={n-1 \choose m-1}$. It
is obvious that at most one color class of $f$ is intersecting,
otherwise, there exists a common vertex in two distinct color
classes, which is a contradiction. Now, there are two cases:
\\

Case I) The case that there exists an intersecting color class of
$f$ and all the other color classes are non-intersecting. Thus,
Hilton-Milner theorem implies that ${n \choose m}-{n-1 \choose
m-1}\leq (k-1)h_{n,m}$ and therefore, $k\geq \left\lceil\frac{{n-1
\choose m}}{1+{n-1 \choose m-1}-{n-m-1 \choose
m-1}}\right\rceil+1$.
\\

Case II) The case that all color classes of $f$ are
non-intersecting. In this case, Hilton-Milner theorem implies
that ${n \choose m}\leq kh_{n,m}$ and $k\geq \left\lceil\frac{{n
\choose m}}{1+{n-1 \choose m-1}-{n-m-1
\choose m-1}}\right\rceil$. \\

Since $\left\lceil\frac{{n \choose m}}{1+{n-1 \choose m-1}-{n-m-1
\choose m-1}}\right\rceil\geq \left\lceil\frac{{n-1 \choose
m}}{1+{n-1 \choose m-1}-{n-m-1 \choose m-1}}\right\rceil+1$, in
both cases, $$k\geq \left\lceil\frac{{n-1 \choose m}}{1+{n-1
\choose m-1}-{n-m-1 \choose m-1}}\right\rceil+1.$$ Therefore, we
have proved the following theorem.

\begin{theorem}{ If $n,m\in \mathbb{N}$ and $n\geq 2m$ and ${\rm
Fall}(KG(n,m))\neq\emptyset$, then $$\left\lceil\frac{{n-1
\choose m}}{1+{n-1 \choose m-1}-{n-m-1 \choose m-1}}\right\rceil+1
\leq\chi_{f}(KG(n,m))\leq\psi_{f}(KG(n,m))\leq{n \choose m}-{n-m
\choose m}$$.}
\end{theorem}



Characterizing ${\rm Fall}(KG(n,m))$ is open in general.
\\
\\
\textbf{Acknowledgements}
\\
\\
The author wishes to thank Ali Jamalian who introduced him the
subject of fall coloring and the reference \cite{dun}. Also, he
would like to thank Hossein Hajiabolhassan, Meysam Alishahi and
Ali Taherkhani for their useful comments.


\begin{thebibliography}{11}


\bibitem{MR2096633}
W. Dong and B. G. Xu.
\newblock Fall colorings of {C}artesian product graphs and regular graphs.
\newblock {\em J. Nanjing Norm. Univ. Nat. Sci. Ed.}, 27(3):17--21, 2004.

\bibitem{MR2193924}
N. Drake, R. Laskar, J. Lyle,
\newblock Independent domatic partitioning or fall coloring of strongly chordal
  graphs.
\newblock {\em Congr. Numer.}, 172:149--159, 2005.
\newblock 36th Southeastern International Conference on Combinatorics, Graph
  Theory, and Computing.


\bibitem{dun} J. E. Dunbar, S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs, J. Knisely, R. C. Laskar, D. F. Rall, Fall colorings of graphs, {\em J. Combin. Math. Combin. Comput}\ {\bf
33}(2000), 257-273. papers in honor of Ernest J. Cockayne.


\bibitem{hil} A. J. W. Hilton, E. C. Milner, Some intersection theorems for systems of finite sets, {\em Quart. J. Math. Oxford (2)}\ {\bf
18}(1967), 369-384.

\bibitem{haj} H. Hajiabolhassan, On the b-chromatic number of Kneser graphs, {\em http://arXiv.org}\ .

\bibitem{jav} R. Javadi, B. Omoomi, On b-coloring of the
Kneser graphs, {\em Discrete Mathematics}\ {\bf 309}(2009),
4399-4408.

\bibitem{irv} R. W. Irving, D. F. Manlove, The b-chromatic number of a graph, {\em Discrete Applied Mathematics}\ {\bf
91}(1999), 127-141.

\bibitem{jav} R. Javadi, B. Omoomi, On b-coloring of the Kneser graphs, {\em Discrete Mathematics}\ {\bf
309}(2009), 4399-4408.

\bibitem{KG} M. Kneser, Aufgabe 300, {\em Jber. Deutsch. Math.-Verein.,}\ {\bf
58}(1955), 27.

\bibitem{las} R. Laskar, J. Lyle, Fall coloring of bipartite graphs and cartesian products of graphs, {\em Discrete Applied Mathematics}\ {\bf
157}(2009), 330-338.

\bibitem{lov} L. Lov{\'a}sz, Kneser's conjecture, chromatic number, and homotopy, {\em Journal of Combinatorial Theory, Ser. A,}\ {\bf
25}(1978), 319-324.




\end{thebibliography}

\end{document}

\bibliographystyle{plain}
\bibliography{aaa}

0909.2772.extracted_bib
\begin{thebibliography}{11}


\bibitem{MR2096633}
W. Dong and B. G. Xu.
\newblock Fall colorings of {C}artesian product graphs and regular graphs.
\newblock {\em J. Nanjing Norm. Univ. Nat. Sci. Ed.}, 27(3):17--21, 2004.

\bibitem{MR2193924}
N. Drake, R. Laskar, J. Lyle,
\newblock Independent domatic partitioning or fall coloring of strongly chordal
  graphs.
\newblock {\em Congr. Numer.}, 172:149--159, 2005.
\newblock 36th Southeastern International Conference on Combinatorics, Graph
  Theory, and Computing.


\bibitem{dun} J. E. Dunbar, S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs, J. Knisely, R. C. Laskar, D. F. Rall, Fall colorings of graphs, {\em J. Combin. Math. Combin. Comput}\ {\bf
33}(2000), 257-273. papers in honor of Ernest J. Cockayne.


\bibitem{hil} A. J. W. Hilton, E. C. Milner, Some intersection theorems for systems of finite sets, {\em Quart. J. Math. Oxford (2)}\ {\bf
18}(1967), 369-384.

\bibitem{haj} H. Hajiabolhassan, On the b-chromatic number of Kneser graphs, {\em http://arXiv.org}\ .

\bibitem{jav} R. Javadi, B. Omoomi, On b-coloring of the
Kneser graphs, {\em Discrete Mathematics}\ {\bf 309}(2009),
4399-4408.

\bibitem{irv} R. W. Irving, D. F. Manlove, The b-chromatic number of a graph, {\em Discrete Applied Mathematics}\ {\bf
91}(1999), 127-141.

\bibitem{jav} R. Javadi, B. Omoomi, On b-coloring of the Kneser graphs, {\em Discrete Mathematics}\ {\bf
309}(2009), 4399-4408.

\bibitem{KG} M. Kneser, Aufgabe 300, {\em Jber. Deutsch. Math.-Verein.,}\ {\bf
58}(1955), 27.

\bibitem{las} R. Laskar, J. Lyle, Fall coloring of bipartite graphs and cartesian products of graphs, {\em Discrete Applied Mathematics}\ {\bf
157}(2009), 330-338.

\bibitem{lov} L. Lov{\'a}sz, Kneser's conjecture, chromatic number, and homotopy, {\em Journal of Combinatorial Theory, Ser. A,}\ {\bf
25}(1978), 319-324.




\end{thebibliography}