% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P33}{20(1)}{2013}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

\usepackage{pstricks}
\usepackage{pst-node}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\newcommand{\modulo}[1]{\hspace{1ex}(\hspace{-1.5ex} \mod {#1})}
\newcommand{\ov}{\overline}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf New approach to the\\ $k$-independence number of a graph}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Yair Caro\\
\small Dept. of Mathematics and Physics\\[-0.8ex]
\small University of Haifa-Oranim\\[-0.8ex] 
\small Tivon 36006, Israel\\
\small\tt yacaro@kvgeva.org.il\\
\and
Adriana Hansberg\thanks{Supported by a Juan de la Cierva Postdoctoral Fellowship; also supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund (ERDF) under project MTM2011-28800-C02-02; and under the Catalonian Government project 1298 SGR2009}\\
\small Dep. de Matem\`atica Aplicada III\\[-0.8ex]
\small UPC Barcelona\\[-0.8ex]
\small 08034 Barcelona, Spain\\
\small\tt adriana.hansberg@upc.edu
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Aug 22, 2012}{Feb 4, 2013}{Feb 12, 2013}\\
\small Mathematics Subject Classifications: 05C69}

\begin{document}

\maketitle


\begin{abstract}
Let $G = (V,E)$ be a graph and $k \ge 0$ an integer. A $k$-independent set $S \subseteq V$ is a set of vertices such that the maximum degree in the graph induced by $S$ is at most $k$. With $\alpha_k(G)$ we denote the maximum cardinality of a $k$-independent set of $G$. We prove that, for a graph $G$ on $n$ vertices and average degree $d$, $\alpha_k(G) \ge \frac{k+1}{\lceil d \rceil + k + 1} n$, improving the hitherto best general lower bound due to Caro and Tuza [Improved lower bounds on k-independence, J. Graph Theory 15 (1991), 99--107].

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} $k$-independence; average degree
\end{abstract}

 %%%%%%%%%%%%%%%%%%%% SECTION 1 %%%%%%%%%%%%%%%%%%%%

\section{Introduction}

Let $G = (V,E)$ be a graph on $n$ vertices and $k \ge 0$ an integer. A \emph{$k$-independent set} $S \subseteq V$ is a set of vertices such that the maximum degree in the graph induced by $S$ is at most $k$. With $\alpha_k(G)$ we denote the maximum cardinality of a $k$-independent set of $G$ and it is called the \emph{$k$-independence number} of $G$. In particular, $\alpha_0(G) = \alpha(G)$ is the usual independence number of $G$. The Caro-Wei bound $\alpha(G) \ge \sum_{v \in V} \frac{1}{\deg(v)+1}$  \cite{Caro, Wei} is an improvement of the well-known Tur\'an bound for the independent number $\alpha(G) \ge \frac{n}{d(G)+1}$ \cite{Tur}, where $d(G)$ is the average degree of $G$. Various results concerning possible improvements and generalizations of the Caro-Wei bound are known (see \cite{AjKoSz1, AlKaSe, AlSp, BCHN, BGHR, GHRSch, Gri, HaRa, HaSch, Mur, Sel, Shea1, Shea2}). A well known generalization to the $k$-independence number of $r$-uniform hypergraphs was obtained by Caro and Tuza \cite{CaTu} improving earlier results of Favaron \cite{Fav} and was extended to non-uniform hypergraphs by Thiele \cite{Thi}. See also the recent papers \cite{CFHV_survey, CPS} for updates. An extension of the notion of residue of a graph, notably developed by Fajtlowicz in \cite{Faj} and Favaron et al. in \cite{FaMaSa}, to the notion of $k$-residue has been developed by Jelen \cite{Jel}. There has been also much interest in using the Caro-Tuza theorem to algorithmic aspects (see \cite{HaLa, Los, ShaSri}). Yet all these lower bounds give asymptotically $\alpha_k(G)\ge \frac{k+2}{2(d+1)}n$ for $k$ fixed and $d = d(G)$. It is easy to see that in general we cannot hope to get better than $\frac{k+1}{d+1}n$, as can be seen from the graph $G = mK_{d+1}$,  consisting of $m$ disjoint copies of the complete graph $K_{d+1}$ and where $d \ge k$ and $n = m(d+1)$. So there is still an asymptotic multiplicative gap of a factor of $2\frac{k+1}{k+2}$. It is worth to mention that there is no known modification of the charming probabilistic proof of the lower bound of Caro-Wei theorem to the situation of $k$-independence that gives a better bound than the Caro-Tuza lower bound. Here, for the sake of being self-contained and to use the same notation, we restate and give the short proof of the Caro-Tuza theorem for graphs. Then we show how to improve this result using further ideas and, in particular, we close the multiplicative gap proving, as a corollary of our main result, that $\alpha_k(G) \ge \frac{k+1}{\lceil d(G) \rceil +k +1} n$. Doing so, we solve a ``folklore" conjecture stated explicitly in \cite{BCHN}.

All along this paper, we will use the following notation and definitions. Let $G$ be a graph. By $V(G)$ we denote the set of vertices of $G$ and $n(G) = |V(G)|$ is the order of $G$. $E(G)$ stands for the set of edges of $G$ and $e(G)$ denotes its cardinality. For a vertex $v \in V(G)$, $\deg(v) = \deg_G(v)$ is the degree of $v$ in $G$. By $\Delta(G)$ we denote the maximum degree of $G$ and by $d(G)$ the average degree $\frac{1}{n(G)} \sum_{v \in V(G)} \deg(v)$. For a subset $S \subseteq V(G)$, we write $G[S]$ for the graph induced by $S$ in $G$ and $\deg_S(v)$ stands for the degree $\deg_{G[S]}(v)$ of $v$ in $G[S]$. Lastly, for a vertex $v \in V(G)$, $G-v$ represents the graph $G$ without vertex $v$ and all the edges incident to $v$ and, for an integer $m \ge 1$, $mG$ is the graph consisting of $m$ disjoint copies of $G$.
%K_n

The paper is divided into five sections. After this introduction section, we deal in Section~2 with a first naive approach to obtain a lower bound on $\alpha_k(G)$ by deleting iteratively vertices of maximum degree until certain point where an old theorem of Lov\'asz \cite{Lov} is applied. In Section~3, we proceed the same way, taking however a better control on the number of vertices that are deleted and we prove that, for a graph $G$ on $n$ vertices and average degree $d$, $\alpha_k(G) \ge \frac{k+1}{\lceil d \rceil + k + 1} n$, improving the hitherto best general lower bound due to Caro and Tuza. For this purpose, we define a parameter $f(k,d)$ which approaches from below the best possible ratio $\frac{\alpha(G)}{n(G)}$ for graphs $G$ with $d(G) \le d$,  we calculate the exact value of $f(1,d)$ and prove some lower bounds on $f(k,d)$. In Section 4, we develop some upper bounds on $f(k,d)$. Finally, we present in Section 5 some open problems for further research.




%%%%%%%%%%%%%%%%%%%% SECTION 2 %%%%%%%%%%%%%%%%%%%%

\section{The naive approach: first improvement}

Let $f_k: [0,\infty) \rightarrow \mathbb{R}$ be the function defined by
$$
f_k(x) = \begin{cases}
1-\frac{x}{2(k+1)}, & \text{if } 0 \le x \le k+1\\
\frac{k+2}{2(x+1)}, & \text{if } x \ge k+1.
\end{cases}
$$

Observe the following properties of $f_k(x)$:

\begin{enumerate}
\item[(P1)] $f_k(x)$ is a convex function and is strictly monotone decreasing on $[0, \infty)$.
\item[(P2)] $f_k(i) - f_k(i+1) \ge f_k(j) - f_k(j+1)$, for $j \ge i \ge 0$.
\item[(P3)] $i f_k(i-1) = (i+1) f_k(i)$, for $i \ge k+1$.
\item[(P4)] $f_k(0) = 1$ and $f_k(k+1) = \frac{1}{2}$.\\
\end{enumerate}

\begin{theorem}[Caro-Tuza for Graphs, \cite{CaTu}] \label{Caro-Tuza}
\sloppy Let $G$ be a graph with degree sequence $d_1, d_2, \ldots,d_n$. Then $\alpha_k(G) \ge \sum_{i = 1}^n  f_k(d_ i)$.
\end{theorem}

\begin{proof}
For a subset $X \subseteq V(G)$, define $s(X) = \sum_{x \in X} f_k(\deg_X(x))$. Among all subsets of $X \subseteq V(G)$ such  that $s(X)$ is maximum, choose $B$ such that $B$ has the smallest cardinality. In particular,  $|B| \ge s(B) \ge s(V(G)) = \sum_{x \in V(G)} f_k(\deg(x))$. We will show that $B$ is a $k$-independent set of G. Suppose there is a vertex $y \in B$ such that $\deg_B(y) = d \ge k +1$. Let $y$ be the vertex of maximum degree in $G[B]$. We will show that $s(B \setminus \{y\}) \ge s(B)$, a contradiction to the minimality of $|B|$. For $x \in B\setminus\{y\}$, let $z(x) = 1$ if $xy$ is an edge in $G$ and $0$ otherwise. Then
\begin{eqnarray*}
s(B \setminus \{y\}) &=& \sum_{x \in B\setminus \{y\}} f_k(\deg_{B\setminus \{y\}}(x)) =  \sum_{x \in B\setminus \{y\}} f_k(\deg_B(x) - z(x))\\
                                 &=&  \left( \sum_{x \in B} f_k(\deg_B(x) - z(x)) \right) - f_k(d)\\
                                 &=& s(B) - f_k(d) +  \sum_{x \in B} (f_k(\deg_B(x) - z(x)) - f_k(\deg_B(x)))\\
                                 &=& s(B) - f_k(d) + \sum_{x \in B} z(x) \left(f_k(\deg_B(x)-1) - f_k(\deg_B(x)) \right)\\
                                 &=& s(B) - f_k(d) + \sum_{x \in B \cap N(y)} \left(f_k(\deg_B(x) -1) - f_k(\deg(x)) \right).
\end{eqnarray*}
With (P2) we obtain that the last term is at least $s(B) - f_k(d) + d(f_k(d-1) - f_k(d)) = s(B) - (d+1) f_k(d) + d f_k(d-1)$ and, since $d f_k(d-1) = (d+1) f_k(d)$ by (P3), this is equal to $s(B)$. It follows that $s(B \setminus \{y\}) \ge s(B)$, which is a contradiction to the choice of $B$. Hence, $B$ is a $k$-independent set and thus
$$\alpha_k(G) \ge |B| \ge s(B) \ge s(V) = \sum_{x \in V(G)} f_k(\deg(x)).$$
\end{proof}

Note that, for $k = 0$, Theorem~\ref{Caro-Tuza} yields the Caro-Wei bound. By convexity, the above bound yields also the following corollary.

\begin{corollary}\label{coro_CT}
For a graph $G$ on $n$ vertices, $\alpha_k(G) \ge f_k(d(G)) n$.
\end{corollary}


Note that, for $k=0$, Corollary~\ref{coro_CT} yields the Tur\'an bound $\alpha(G) \ge \frac{1}{d(G)+1} n$. Also, if $d(G) \ge k+1$, we obtain from this corollary the following one.

\begin{corollary}
Let $G$ be a graph on $n$ vertices. If $d(G) \ge k+1$, then $\alpha_k(G) \ge \frac{k+2}{2(d(G)+1)}n$.
\end{corollary}

For a graph $G$, we will denote with $\chi_k(G)$ the \emph{$k$-chromatic number} of $G$, i.e. the minimum number $t$ such that there is a partition $V(G) = V_1 \cup V_2 \cup \ldots V_t$ of the vertex set $V(G)$ such that $\Delta(G[V_i]) \le k$ for all $1 \le i \le t$. The following theorem is due to Lov\'asz.

\begin{theorem}[Lov\'asz \cite{Lov}, 1966]
Let $G$ be a graph with maximum degree $\Delta$. If $k_1, k_2, \ldots,$ $k_t \ge 0$ are integers such that $\Delta + 1 = \sum_{i=1}^t (k_i+1)$, then there is a partition $V(G) = V_1 \cup V_2 \cup \ldots \cup V_t$ of the vertex set of $G$ such that $\Delta(G[V_i]) \le k_i$ for $1 \le i \le t$.
\end{theorem}

Several proofs and generalizations of Lov\'asz's theorem are known. We refer the reader to \cite{BoMa, BoKoTo, Cat1, Cat2, Rab}. An algorithmic analysis of Lov\'asz theorem with running time $O(n^3)$ is given in \cite{HaLa}. An immediate and well known corollary of Lov\'asz's theorem is Corollary~\ref{cor_Lov}, which is useful in the study of defective colorings also known as improper colorings (see \cite{BHHL, CCW, FrHe, HKS}).


\begin{corollary}\label{cor_Lov}
If $G$ is a graph of maximum degree $\Delta$, then $\chi_k(G) \le \lceil \frac{\Delta+1}{k+1} \rceil$.
\end{corollary}

Since $\alpha_k(G) \ge \frac{n}{\chi_k(G)}$, the following bound proved in 1986 by Hopkins and Staton follows trivially from the above corollary.

\begin{theorem}[Hopkins, Staton \cite{HS} 1986] \label{thm_HS}
Let $G$ be a graph of order $n$ and maximum degree $\Delta$. Then
$$\alpha_k(G)\ge\frac{n}{\left\lceil\frac{\Delta+1}{k+1}\right\rceil}.$$
\end{theorem}

The following theorem is a direct consequence of Theorem~\ref{thm_HS} which generalizes and improves several results concerning relations between $\alpha_p(G)$ and $\alpha_q(G)$ (see e.g. \cite{BCFM}).

\begin{theorem}
Let $G$ be a graph and $q \ge p \ge 0$ two integers. Then $\alpha_q(G) \le \left\lceil \frac{q+1}{p+1} \right\rceil \alpha_p(G)$.
\end{theorem}

\begin{proof}
Let $S$ be a maximum $q$-independent set of $G$. Then $\Delta(G[S]) \le q$ and, by Theorem~\ref{thm_HS},
$$\alpha_p(G) \ge \alpha_p(G[S]) \ge \frac{|S|}{\left\lceil \frac{\Delta(G[S])+1}{p+1} \right\rceil} \ge \frac{\alpha_q(G)}{\left\lceil \frac{q+1}{p+1} \right\rceil},$$
which implies the statement.
\end{proof}


Completing $\Delta + 1$ to the next multiple of $k+1$, the following observation is straightforward from Theorem~\ref{thm_HS}.

\begin{observation}\label{obs_HS}
Let $G$ be a graph of order $n$ and maximum degree $\Delta$ and let $r$ be an integer such that $0 \le r \le k$ and $\Delta+1+r\equiv 0 \modulo{k+1}$. Then
$$\alpha_k(G)\ge \frac{k+1}{\Delta+r+1}n.$$
\end{observation}

\begin{proof}
As clearly $\lceil\frac{\Delta+1}{k+1}\rceil = \frac{\Delta+r+1}{k+1}$, Theorem~\ref{thm_HS} implies then $\alpha_k(G)\ge \frac{k+1}{\Delta+r+1}n.$
\end{proof}

When the graph is $d$-regular, we can set $\Delta = d = d(G)$ in Observation~\ref{obs_HS} and we obtain the following one.

\begin{observation}
Let $G$ be a $d$-regular graph on $n$ vertices and let $r$ be an integer such that $0 \le r \le k$ and $d+1+r\equiv 0 \modulo{k+1}$. Then $\alpha_k(G)\ge \frac{k+1}{d+r+1}n.$
\end{observation}

So this observation shows that indeed, for $d$-regular graphs, we can close the multiplicative gap of $2\frac{k+1}{k+2}$ using Lov\'asz's theorem. This serves as an inspiration to trying to close the multiplicative gap in general.

Note that, in practice, the Hopkins-Staton bound can be poor if the maximum degree is far from the average degree.
So, our first naive strategy will be to delete a vertex with large degree and, if possible, use induction on the number of vertices. Otherwise, if $\Delta(G)$ is near to the average degree $d(G)$, we will apply Theorem~\ref{thm_HS}. This is precisely what is done in the next result.

\begin{theorem}\label{1st_approach}
Let $G$ be a graph on $n$ vertices. Then $\alpha_k(G) >  \frac{k+1}{d(G) +2k +2}n$.
\end{theorem}

\begin{proof}
We will proceed by induction on $n$. If $n=1$, the statement is trivial. If $n=2$, $G$ is either $K_2$ or $\ov{K_2}$. If $G=K_2$, then $d(G) = 1$ and $\frac{k+1}{d(G) +2k +2}n = \frac{2(k+1)}{3+2k} < 1 \le \alpha_k(G)$ for any $k \ge 0$. If $G = \ov{K_2}$, then $d(G) = 0$ and thus $\frac{k+1}{d(G) +2k +2}n = 1 < 2 = \alpha_k(G)$ for all $k \ge 0$. Suppose now that $n \ge 3$ and that the statement holds for $n-1$. Let $G$ be a graph on $n$ vertices and $v \in V(G)$ a vertex of maximum degree $\Delta$. Define $G^* = G - v$. Since any $k$-independent set of $G^*$ is also a $k$-independent set of $G$, $\alpha_k(G) \ge \alpha_k(G^*)$. We distinguish two cases.\\
\emph{Case 1. Suppose that $\Delta \le \lceil d(G) \rceil +k$.} Then, by Observation~\ref{obs_HS}, we have
$$\alpha_k(G) \ge \frac{k+1}{\Delta+k+1} n \ge \frac{k+1}{\lceil d(G) \rceil + 2k +1}n > \frac{k+1}{d(G) + 2k + 2}n$$
and we are done.\\
\emph{Case 2. Suppose that $\Delta \ge \lceil d(G) \rceil +k+1$.} By induction and with $\Delta \ge \lceil d(G) \rceil + k+1 \ge d(G)+k+1$, we obtain 
\begin{eqnarray*}
\alpha_k(G)\; \ge \; \alpha_k(G^*) &>& \frac{(k+1)(n-1)}{d(G^*) + 2k+2}  = \frac{(k+1)(n-1)}{\frac{2 e(G^*)}{n-1}+2k+2} \\
                       &=& \frac{(k+1)(n-1)}{\frac{2 e(G) - 2 \Delta}{n-1}+2k+2} = \frac{(k+1)(n-1)}{\frac{d(G) n - 2 \Delta}{n-1}+2k+2}\\
&\ge&  \frac{(k+1)(n-1)}{\frac{d(G) n - 2 (d(G)+k+1)}{n-1}+2k+2} 
                       = \frac{(k+1)n}{(d(G)+2 k+2) \frac{(n-2)n}{(n-1)^2}}\\
                       & >& \frac{k+1}{ d(G)+2k+2}n
\end{eqnarray*}
and the statement follows.
\end{proof}

Note that the bound in the previous theorem is better than the Caro-Tuza bound for $k=1$ and $d \ge 8$ and for $k \ge 2$ and $d \ge 2k+5$. Note also that Theorem~\ref{1st_approach} already closes the multiplicative factor of $2\frac{k+1}{k+2}$ for fixed $k$ as $d(G)$ grows. However, to obtain an even better lower bound, we need to get more control on the number of vertices of large degrees that are deleted and to apply Observation~\ref{obs_HS} in its full accuracy. This will be done in the next section. 

We close this section with the following algorithm for obtaining a $k$-independent set of cardinality at least $\frac{k+1}{d(G) +2k +2}n$ for any graph $G$ on $n$ vertices that yields us the proof of Theorem~\ref{1st_approach}.\\

\noindent
{\bf Algorithm 1}\\[1ex]
INPUT: a graph $G$ on $n$ vertices and $m$ edges.\\[-3ex]
\begin{itemize}
\item[(1)] Compute $\Delta(G)$ and $d(G)$. GO TO (2).
\item[(2)] If $\Delta(G) \le \lceil d(G) \rceil + k$, perform a Lov\'asz partition into $k$-independent sets, choose the largest class $S$ and END. Otherwise choose a vertex $v$ of maximum degree $\Delta(G)$, set $G:= G - v$ and GO TO (1).\\[-3ex]
\end{itemize}  
OUTPUT: $S$

\bigskip

The algorithm terminates as, at some step, $\Delta(G) \le \lceil d(G) \rceil + k$ must hold (the latest when $G$ is the empty graph). As already mentioned, the Lov\'asz partition requires a running time of $O(n^3)$, while each other step takes at most $O(n)$ time and the number of iteration steps before performing Lov\'asz partition is at most $n$. Hence, the algorithm runs in at most $O(n^3)$ time.

%%%%%%%%%%%%%%%%%%%% SECTION 3 %%%%%%%%%%%%%%%%%%%%

\section{Deletions, partitions and a better lower bound on $\alpha_k(G)$ - second improvement}

\begin{definition}
Let $d, k \ge 0$ be two integers. We define $$f(k,d) = \inf \left\{ \frac{\alpha_k(G)}{n(G)} : G \mbox{ is a graph with } d(G) \le d\right\}.$$
\end{definition}

\begin{observation}
Let $d, k \ge 0$ be two integers. For every graph $G$ on $n$ vertices and average degree $d(G) \le d$, $\alpha_k(G) \ge f(k,d) n$.
\end{observation}

The next theorem shows that $f(k,d)$ is convex as a function of $d$. 

\begin{theorem}
Let $d, k, t \ge 0$ be integers and $t \le d$. Then $2f(k,d) \le f(k,d-t) + f(k,d+t)$.
\end{theorem}

\begin{proof}
We will show that for any two graphs $G_1$ and $G_2$ such that $d(G_1) \le d-t$ and $d(G_2) \le d+t$, there is a graph $G$ with $d(G) \le d$ such that $2 \frac{\alpha_k(G)}{n(G)} \le \frac{\alpha_k(G_1)}{n(G_1)} + \frac{\alpha_k(G_2)}{n(G_2)}$. Let $G_1$ and $G_2$ be such graphs and let $n(G_i) = n_i$ and $V(G_i) = V_i$, $i = 1,2$. Define the graph $G = n_2 G_1 \cup n_1 G_2$. Then
\begin{eqnarray*}
2n_1n_2 d(G) = n(G) d(G) &=& n_2 \sum_{x \in V_1} \deg_{G_1}(x) + n_1 \sum_{y \in V_2} \deg_{G_2}(y)\\
                                                &=& n_2 n_1 d(H_1) + n_1 n_2 d(G_2) \\
                                                &\le& n_2 n_1 (d-t) + n_1 n_2 (d+t) = 2 n_1 n_2 d,
\end{eqnarray*}
implying that $d(G) \le d$ and thus $f(k,d) \le \frac{\alpha_k(G)}{n(G)}$. Moreover,
$$
2f(k,d) \le 2 \frac{\alpha_k(G)}{n(G)} = \frac{n_2 \alpha_k(G_1) + n_1 \alpha_k(G_2)}{n_1n_2}
= \frac{\alpha_k(G_1)}{n_1} + \frac{\alpha_k(G_2)}{n_1}.
$$
As $G_1$ and $G_2$ were arbitrarily chosen, it follows that $2f(k,d) \le f(k,d-t) + f(k,d+t)$.
\end{proof}

Before coming to the main theorems of this section, we need the following lemmas.

\begin{lemma}\label{lem_subg}
Let $d, t \ge 0$ be two integers and let $G$ be a graph on $n$ vertices with average degree $d(G) \le d$. Then $G$ has a subgraph $H$ such that either  $\Delta(H) \le d+t-1$ and $n(H) \ge n - \lfloor \frac{n}{d+2t+1}\rfloor$ or $d(H) \le d-1$ and $n(H) = n - \lceil \frac{n}{d+2t+1} \rceil$.
\end{lemma}

\begin{proof}
For an $r \ge0$, let $\{v_1, v_2, \ldots, v_r\}$ be a set of vertices of maximum cardinality such that $\deg_{G_{i+1}}(v_i) \ge d+t$, where $G_{i+1} = G_i - v_i$ and $G_0 = G$. Suppose first that $r \le \lfloor \frac{n}{d+2t+1} \rfloor$ and let $H = G_{r+1}$. Then $H$ has at least $n - r \ge n - \lfloor \frac{n}{d+2t+1} \rfloor$ vertices and $\Delta(H) \le d+t-1$. Now suppose that $r \ge \lceil \frac{n}{d+2t+1} \rceil$. Let now $H = G_{q+1}$, where $q = \lceil \frac{n}{d+2t+1} \rceil$. Then $n(H) = n - \lceil \frac{n}{d+2t+1} \rceil$. Further,
\begin{eqnarray*}
d(H) = \frac{2 e(H)}{n(H)} \le \frac{2(e(G) - (d+t)q)}{n-q} \le \frac{dn - 2(d+t)q}{n-q} = \frac{d(n-\frac{2(d+t)}{d}q)}{n-q}.
\end{eqnarray*}
Since, for any real numbers $a \ge 0$ and $b \ge 1$, the function $\frac{a - bx}{a-x}$ is monotonically decreasing in $[0, \infty)$, setting $a = n$ and $b = \frac{2(d+t)}{d}$, we obtain with $q = \lceil \frac{n}{d+2t+1} \rceil \ge \frac{n}{d+2t+1}$
\begin{eqnarray*}
d(H) &\le& \frac{d(n-\frac{2(d+t)}{d}q)}{n-q} \le \frac{d(n- \frac{2(d+t)}{d} \frac{n}{d+2t+1})}{n- \frac{n}{d+2t+1}}\\
&=& \frac{d(d+2t+1) - 2(d+t)}{d+2t} = \frac{d(d+2t) - (d+2t)}{d+2t} = d-1.
\end{eqnarray*}
Hence, we have shown that $G$ has a subgraph $H$ with either $d(H) \le d-1$ and $n(H) = n - \lceil \frac{n}{d+2t+1} \rceil$ or $\Delta(H) \le d+t-1$ and $n(H) = n - \lfloor \frac{n}{d+2t+1}\rfloor$.
\end{proof}

The following corollary is straightforward from this lemma.

\begin{corollary}\label{cor_subg}
Let $d, t \ge 0$ be two integers. Let $G$ be a graph on $n$ vertices with average degree $d(G) \le d$ and such that $d+2t+1$ divides $n$. Then $G$ has a subgraph $H$ on $n(H) \ge \frac{d+2t}{d+2t+1}n$ vertices such that either $d(H) \le d-1$ or $\Delta(H) \le d+t-1$.
\end{corollary}

%\smallskip

\begin{lemma}\label{div}
Let $G$ be a graph on $n$ vertices with average degree $d(G) \le d$ and such that $d+2s+1$ does not divide $n$. Then there is a graph $H$ such that $d+2s+1$ divides $m = n(H)$, $d(H) = d(G) \le d$ and $\frac{\alpha_k(H)}{m} = \frac{\alpha_k(G)}{n}$.
\end{lemma}

\begin{proof}
Let $H = (d+2s+1) G$. Then $m = n(H) = (d+2s+1)n$ is multiple of $d+2s+1$, $d(H) = d(G)$ and $\frac{\alpha_k(H)}{m} = \frac{(d+2s+1) \alpha_k(G)}{(d+2s+1)n} = \frac{\alpha_k(G)}{n}$.
\end{proof}

Let $n$ be an even integer. We denote by $J_n$ the graph consisting of a complete graph on $n$ vertices minus a $1$-factor. We are now ready to present the exact value of $f(1,d)$ and the consequences of this result. 

\begin{theorem}\label{thm_k=1}
Let $d \ge 0$ be an integer. Then the following statements hold.
\begin{itemize}
\item[(1)] 
$f(1,d) = \begin{cases} \frac{2}{d+2}, &\text{if } d \equiv 0 \modulo{2}\\
                                                          \frac{2(d+2)}{(d+1)(d+3)}, &\text{if } d \equiv 1 \modulo{2}.
                                \end{cases}$
\item[(2)] The equality $f(1,d) = \frac{\alpha_1(G)}{n(G)}$ is attained by the graph $G = J_{d+2}$, when $d$ is even, and by $G=(d+3) J_{d+1} \cup (d+1) J_{d+3}$, when $d$ is odd.
\item[(3)] $f(1,d) \ge \frac{2}{d+2}$.
\item[(4)] For every graph $G$ on $n$ vertices, $\alpha_1(G) \ge \frac{2n}{\lceil d(G) \rceil +2}$.
\end{itemize}
\end{theorem}

\begin{proof}
(1) We will prove by induction on $d$ that 
$$f(1,d) \ge \begin{cases} \frac{2}{d+2}, &\text{if } d \equiv 0 \modulo{2}\\
                                                          \frac{2(d+2)}{(d+1)(d+3)}, &\text{if } d \equiv 1 \modulo{2}.
                                \end{cases}$$
For $d = 0$, clearly $f(1,0) = 1 = \frac{2}{0+2}$, as the only possible graph $G$ with $d(G) \le 0$ is the empty graph. For $d=1$, let $G$ be a graph with $d(G) \le 1$. Setting $s=1$, we can suppose by Lemma~\ref{div} that $4$ divides $n(G) = n$. Hence, Corollary~\ref{cor_subg} implies that there is a subgraph $H$ of $G$ on $n(H) \ge \frac{3}{4}n$ vertices with $d(H) \le 0$ or $\Delta(H) \le 1$. In both cases we have clearly $\alpha_1(G) \ge \alpha_1(H) = n(H) \ge \frac{3}{4}n$ and hence $f(1,1) = \inf\{\frac{\alpha_1(G)}{n(G)} : G \mbox{ graph with } d(G) \le 1 \} \ge \frac{3}{4}= \frac{2(1+2)}{(1+1)(1+3)}$. \\
Assume we have proved the statement for $f(1,d-1)$. Now we will prove it for $f(1,d)$, where $d > 1$. Let $G$ be a graph on $n$ vertices such that $d(G) \le d$. We distinguish two cases.\\
\emph{Case 1. Suppose that $d \equiv 0 \modulo{2}$.} Setting $s=0$, we can suppose by Lemma~\ref{div} that $d+1$ divides $n$. By Corollary~\ref{cor_subg}, there is a subgraph $H$ of $G$ on at least $\frac{d}{d+1}n$ vertices with either $d(H) \le d-1$ or $\Delta(H) \le d-1$. Hence, in both cases $d(H) \le d-1$ and thus, by induction, we have 
$$\alpha_1(G) \ge \alpha_1(H) \ge f(1,d-1) n(H) \ge  \frac{2(d+1)d}{d(d+2)(d+1)} n = \frac{2}{d+2}n.$$
Hence, $f(1,d) =  \inf\{\frac{\alpha_1(G)}{n(G)} : G \mbox{ graph with } d(G) \le d \} \ge \frac{d}{d+2}$ and we are done.\\
\emph{Case 2. Suppose that $d \equiv 1 \modulo{2}$.} Set $s =1$. By Lemma~\ref{div}, we can suppose that $d+3$ divides $n$. By Corollary~\ref{cor_subg}, there is a subgraph $H$ of $G$ on at least $\frac{d+2}{d+3}n$ vertices with either $d(H) \le d-1$ or $\Delta(H) \le d$. If $d(H) \le d-1$, we can apply the induction hypothesis on $H$ and we obtain
$$\alpha_1(G) \ge \alpha_1(H) \ge f(1,d-1) n(H) \ge  \frac{2(d+2)}{(d+1)(d+3)} n$$
and we are done. Suppose finally that $\Delta(H) \le d$. Then, by Theorem~\ref{thm_HS} and as $d$ is odd, we have
$$\alpha_1(G) \ge \alpha_1(H) \ge \frac{n(H)}{\left\lceil \frac{\Delta(H) + 1}{2} \right\rceil} \ge \frac{ \frac{d+2}{d+3}n }{\left\lceil \frac{d + 1}{2}\right\rceil}=  \frac{2(d+2)}{(d+1)(d+3)} n.$$
Thus, in both cases, $f(1,d) = \inf\{\frac{\alpha_1(G)}{n(G)} : G \mbox{ graph with } d(G) \le d \} \ge \frac{2(d+2)}{(d+1)(d+3)}$
Hence, by induction, the statement holds.\\
Let $d$ be even. Clearly $\alpha_1(J_{d+2})= 2$ and hence, $f(1,d) \le \frac{\alpha_1(J_{d+2})}{d+2} = \frac{2}{d+2}$. For $d$ odd, the graph $G = (d+3) J_{d+1} \cup (d+1) J_{d+3}$ has $\alpha_1(G) = (d+3) 2 + (d+1)2 = 4(d+2)$. Hence $f(1,d) \le \frac{\alpha_1(G)}{n(G)} =  \frac{4(d+2)}{2(d+1) (d+3)}$. Together with the inequalities proven above, it follows
$$f(1,d) = \begin{cases} \frac{2}{d+2}, &\text{if } d \equiv 0 \modulo{2}\\
                                                          \frac{2(d+2)}{(d+1)(d+3)}, &\text{if } d \equiv 1 \modulo{2}.
                                \end{cases}$$
(2) This follows from the discussion in (1).\\
(3) It is easily seen that $\frac{2(d+2)}{(d+1)(d+3)} \ge \frac{2}{d+2}$. Hence we have always $f(1,d) \ge \frac{2}{d+2}$.   \\
(4) From item (3), we obtain $\alpha_1(G) \ge f(1, \lceil d(G) \rceil) n \ge \frac{2}{\lceil d(G) \rceil+2}$ n.                    
\end{proof}


We can now state and prove our main result generalizing the proof of Theorem~\ref{thm_k=1} to arbitrary $k$ and $d$.

\begin{theorem}\label{main}
Let $d, k \ge 0$ be two integers. Then the following statements hold.
\begin{itemize}
\item[(1)] $f(k,d) \ge \frac{(k+1)(d+2t)}{(d+k+t+1)(d+t)} \ge \frac{k+1}{d+k+1}$, where $t$ is such that $d \equiv k+1 - t  \modulo{k+1}$ and $1 \le t \le k+1$.
\item[(2)] For $k \ge d$, $f(k,d) \ge \frac{2k+2-d}{2k+2}$. For $k \ge d = 1$, the bound is realized by the graph $K_{1,k+1} \cup kK_1$ and thus $f(k,1) = \frac{2k+1}{2k+2}$.
\item[(3)] For any graph $G$ on $n$ vertices, $\alpha_k(G) \ge \frac{k+1}{\lceil d(G) \rceil + k+1} n$.
\end{itemize}
\end{theorem}

\begin{proof}
(1) We will proceed to prove the inequality $f(k,d) \ge \frac{(k+1)(d+2t)}{(d+k+t+1)(d+t)}$ by induction on $d$. If $d=0$, then $d \equiv (k+1) - (k+1)$ and clearly $f(k,0) = 1 = \frac{(k+1) (0 + 2(k+1))}{(0+k+(k+1)+1) (0+(k+1))}$, as the only possible graph $G$ with $d(G) \le 0$ is the empty graph. 


Assume $f(k,d-1) \ge \frac{(k+1)(d-1+2t')}{(d+k+t')(d-1+t')}$, where $d-1 \equiv k+1 - t' \modulo{k+1}$, $1 \le t' \le k+1$, and $d \ge 1$. We will prove the statement for $d$. Herefor, we distinguish two cases.\\
\emph{Case 1. Suppose that $d \equiv 0 \modulo{k+1}$.} Then $t = k+1$. Let $G$ be a graph on $n$ vertices such that $d(G) \le d$. By Lemma~\ref{div}, setting there $s=0$, we can suppose that $d+1$ divides $n$. Then from Corollary~\ref{cor_subg} it follows that there is a subgraph $H$ of $G$ on at least $\frac{d}{d+1}n$ vertices such that $d(H) \le d-1$ or $\Delta(H) \le d-1$. In both cases we have $d(H) \le d-1$. Then, as $d-1 \equiv (k+1) - 1 \modulo{k+1}$, we obtain by induction
\begin{eqnarray*}
\alpha_k(G) &\ge& \alpha_k(H) \ge \frac{(k+1)(d+1)}{(d+k+1)d} n(H) \ge \frac{k+1}{d+k+1}n \\ 
&=& \frac{(k+1)(d+2t)}{(d+2t)(d+k+1)}n = \frac{(k+1)(d+2t)}{(d+k+t+1)(d+t)}n.
\end{eqnarray*}
Thus, $f(k,d) =  \inf\{\frac{\alpha_k(G)}{n(G)} : G \mbox{ graph with } d(G) \le d \} \ge \frac{(k+1)(d+2t)}{(d+k+t+1)(d+t)}$ and we are done.\\
\emph{Case 2. Suppose that $d \equiv k+1 - t \modulo{k+1}$ for  some $t$ with $1 \le t \le k$.} Using Lemma~\ref{div} with $s=t$, we can suppose that $d+2t+1$ divides $n$.
By Corollary~\ref{cor_subg}, there is a subgraph $H$ of $G$ on $n(H) \ge \frac{d+2t}{d+2t+1}n$ vertices with either $d(H) \le d-1$ or $\Delta(H) \le d+t-1$. If $\Delta(H) \le d+t-1$, then Theorem~\ref{thm_HS} yields
\begin{eqnarray*}
\alpha_k(G) \ge \alpha_k(H) \ge \frac{n(H)}{\left\lceil \frac{\Delta(H)+1}{k+1} \right\rceil} 
                                           \ge \frac{\frac{d+2t}{d+2t+1}n}{\left\lceil \frac{d+t}{k+1} \right\rceil}  
                                           &=& \frac{(k+1)(d+2t)}{(d+2t+1)(d+t)}n\\
                                           &\ge& \frac{(k+1)(d+2t)}{(d+k+t+1)(d+t)} n.
\end{eqnarray*} 
Hence, $f(k,d) =  \inf\{\frac{\alpha_k(G)}{n(G)} : G \mbox{ graph with } d(G) \le d \} \ge \frac{(k+1)(d+2t)}{(d+k+t+1)(d+t)}$                                           
and we are done. Suppose now that $d(H) \le d-1$. Since $d -1 \equiv (k+1) - (t+1)$, we obtain by induction
\begin{eqnarray*}
\alpha_k(G) \ge \alpha_k(H) &\ge& \frac{(k+1)((d-1)+2(t+1))}{((d-1)+k+(t+1)+1)((d-1)+(t+1))} n(H) \\
                                                                    &\ge& \frac{(k+1)(d+2t+1)}{(d+k+t+1)(d+t)}\cdot \frac{d+2t}{d+2t+1} n\\
                                                                    &=& \frac{(k+1)(d+2t)}{(d+k+t+1)(d+t)} n.
\end{eqnarray*} 
Thus, again, $f(k,d) \ge \frac{(k+1)(d+2t)}{(d+k+t+1)(d+k+1)}$ and Case 2 is done. \\
Hence, by induction, the statement holds. Finally, the inequality $ \frac{(k+1)(d+2t)}{(d+k+t+1)(d+t)} \ge \frac{k+1}{d+k+1}$ follows easily.\\
(2) Let $k \ge d$ and let $t$ be such that $d \equiv k+1 - t \modulo{k+1}$ and $1 \le t \le k+1$. Then $d = k+1-t$. Hence, with (1),
\begin{align*}
f(d,k) &\ge  \frac{(k+1)(d+2t)}{(d+k+t+1)(d+t)}\\ 
&= \frac{(k+1)(d+ 2(k+1-d))}{(d+k+(k+1-d)+1)(d+(k+1-d))} = \frac{2k+2-d}{2k+2}.
\end{align*}
Let $G = K_{1,k+1} \cup kK_1$. Then $\alpha_k(G) = 2k+1$, $n(G) = 2k+2$ and $d(G) = \frac{2k+2}{2k+2} = 1$. Hence, $\frac{2k+1}{2k+2} \le f(k,1) \le \frac{\alpha_k(G)}{n(G)} = \frac{2k+1}{2k+2}$, obtaining thus equality.\\
(3) If $G$ is a graph on $n$ vertices, then, using (1), we obtain 
$$\frac{\alpha_k(G)}{n} \ge f(k, \lceil d(G) \rceil) \ge \frac{k+1}{\lceil d(G) \rceil +k+1}.$$
\vskip-18pt
\vskip-1pt
\end{proof}

The proofs of Lemma~\ref{lem_subg} and Theorem~\ref{main} yield us an algorithm for finding, for any graph $G$ on $n$ vertices, a $k$-independent set of cardinality at least $\frac{k+1}{\lceil d(G) \rceil + k+1} n$. It works the following way. It computes $d=d(G)$ and $\Delta(G)$ and finds the integer $t$ such that $0 \le t \le k$ and $d \equiv k+1 - t  \modulo{k+1}$ (note that the case $t=0$ corresponds here to the case $t=k+1$ of Theorem~\ref{main}). Then it checks if the graph satisfies the condition $\Delta(G) \le d+t-1$. If so, then it performs a Lov\'asz partition into $k$-independent sets, selects the largest set from it and gives this as output. If not, then a vertex of maximum degree is deleted and the condition on the maximum degree is checked again on the remaining graph. This deletion step is repeated up to $ \lceil\frac{n}{d+2t+1} \rceil$ times, as, by Lemma~\ref{lem_subg}, if the maximum degree is still larger than $d+t-1$, then we are left with a graph with smaller average degree, with which the algorithm starts over again, doing here the inductive step of Theorem~\ref{main}. \\



\noindent
{\bf Algorithm 2}\\[1ex]
INPUT: a graph $G$ on $n$ vertices and $m$ edges.\\[-4ex]
\begin{itemize}
\item[(1)] Compute $\Delta(G)$ and $d(G)$.  Set $d = \lceil d(G) \rceil$ and determine $t$ such that $0 \le t \le k$ and $d \equiv k+1 - t  \modulo{k+1}$. Set $r:=0$ and  GO TO (2).\\[-20pt]
\item[(2)] If $\Delta(G) \le d+t-1$, perform a Lov\'asz partition into $k$-independent sets, choose the largest class $S$ and END. Otherwise GO TO (3).\\[-20pt]
\item[(3)]  Set $r := r+1$. If $r > \lceil\frac{n}{d+2t+1} \rceil$, set $n := n -  \lceil \frac{n}{d+2t+1} \rceil$ and GO TO (1). Otherwise choose a vertex $v$ of maximum degree $\Delta(G)$, set $G:= G - v$, compute $\Delta(G)$ and GO TO (2). \\[-3.5ex]
\end{itemize}  
OUTPUT: $S$

\bigbreak

The algorithm terminates as, at some step, $\Delta(G) \le \lceil d(G) \rceil +t-1$ must hold (the latest when $G$ is the empty graph).
Again, the algorithm has a running time of at most $O(n^3)$.

%%%%%%%%%%%%%%%%%%%% SECTION 4 %%%%%%%%%%%%%%%%%%%%

\section{Upper bounds on $f(k,d)$ and determination of $f(k,d)$ for further small values}

Observe that after Theorems~\ref{thm_k=1}(1) and \ref{main}(2), we know the exact value of $f(k,d)$ in case $\min\{d,k\} \le 1$. The first pair $(k,d)$ for which an exact value of $f(k,d)$ is not known yet is $(2,2)$. In this section, we develop several upper bounds on $f(k,d)$ as a starting point to future research to obtain further exact values of $f(k,d)$. We will use the following theorem.


\begin{theorem}[see \cite{Bol}, p.108]\label{thm_bol}
Let $r, g \ge 3$ be two integers. If $m$ is an integer with $m \ge \frac{(r-1)^{(g-1)}-1}{r-2}$, then there exists an $r$-regular graph of girth at least $g$ and order $2m$.
\end{theorem}

Define the function $h(r) = \frac{(r-1)^{r+3}-1}{r-2}$. We will use the particular form of this theorem with $m \ge h(r)$, implying that there is an $r$-regular graph of girth at least $r+4$ and order $2m$.

In the proof of the following theorem, we use the following notation. $\overline{G}$ denotes the complementary graph of $G$. If $F \subseteq E(G)$, then $G-F$ represents the graph $G$ without the edges contained in $F$. For a graph $H$ on at most $n$ vertices, $K_n - E(H)$ stands for the complete graph $K_n$ without the edges of a subgraph $H$. Further, given two graphs $G$ and $H$, $G \cup H$ is the graph consisting of one copy of $H$ and one copy of $G$. Finally, the girth of a graph $G$ is denoted by $g(G)$.

\begin{theorem}\label{upper_bounds}
Let $d, k \ge 0$ be two integers. Then the following statements hold.
\begin{itemize}
\item[(1)] For $d \ge k$, $\frac{k+1}{d+k+1} \le f(k,d) \le \frac{k+1}{d+1}$.
\item[(2)] For $d > k$, $d \equiv 0 \modulo{2}$ and $k \equiv 1 \modulo{2}$, $f(k,d) \le \frac{k+1}{d+2}$.
\item[(3)] For $d > k$, $f(k,d) \le \frac{k+2}{d+3}$.
\item[(4)] For $k \ge 3$, $d \ge 2h(k) - k-1$ and $d+k+1 \equiv 0 \modulo{2}$, $f(k,d) \le \frac{k+2}{d+k+1}$.
\item[(5)] For $2 \le d \le 4+6q$, where $q \ge 0$ is an integer, $\frac{3}{d+3} \le f(2,d) \le \frac{3}{d+1+\frac{1}{q+1}}$.
\item[(6)] For $k \ge 2$, $\frac{k}{k+1} \le f(k,2) \le \frac{k+1}{k+2+\frac{1}{k+1}}$.
\item[(7)] For $k \ge 3$, there is a constant $c > 0$ auch that $f(k,d) < \frac{k+2}{d+ c(\frac{d}{2})^{\frac{1}{k+2}} +1}$.
\end{itemize}
\end{theorem}

\begin{proof}
(1) The lower bound follows from Theorem~\ref{main}. The upper bound follows from
$f(k,d) \le \frac{\alpha_k(K_{d+1})}{d+1} = \frac{k+1}{d+1}$.\\
(2) Let $G$ be the graph $K_{d+2}$ minus a $1$-factor (this is possible, as $d$ is assumed even). Then $d(G) = d$. Let $T\subseteq V(G)$ be any subset of $k+2$ vertices. As $k+1 \equiv 0 \modulo{2}$, not every vertex of $T$ is covered by the edges of the $1$-factor in $\overline{G}[T]$. Hence, at least one vertex from $T$ is adjacent in $G$ to all other vertices from $T$. Hence, no subset of $k+2$ vertices can be a $k$-independent set and thus $\alpha_k(G) \le k+1$. This implies $f(k,d) \le \frac{k+1}{d+2}$.\\
(3) Let $d >k$. Consider the graph $G = K_{d+3} - E(C_{d+3})$, where $C_{d+3}$ is a cycle of length $d+3$ in $K_{d+3}$. Then $d(G) =d$. Let $T \subseteq V(G)$ a subset of $k+3$ vertices. Since $k+3 < d+3 = n(G)$, the graph $\overline{G}[T]$ contains no cycles. Hence there is at least one vertex in $v \in V(T)$ which is adjacent in $G[T]$ to all but at most one vertex and hence $\deg_{G[T]}(v) \ge k+1$. This implies that $\alpha_k(G) \le k+2$ and thus $f(k,d) \le \frac{k+2}{d+3}$.\\
(4) Let $k \ge 3$, $d \ge 2h(k) - k-1$ and $d+k+1 \equiv 0 \modulo{2}$. By Theorem~\ref{thm_bol}, there is a $k$-regular graph $H$ with $g(H) \ge k+4$ and $n(H) = d+k+1 = n$. Consider now the graph $G = K_n - E(H)$. Then $d(G) = n-1-k = d$. Let $T \subseteq V(G)$ be a subset of $k+3$ vertices. Since $g(H) \ge k+4$, $\overline{G}[T]$ is a forest. Hence there is at least one vertex in $v \in V(T)$ which is adjacent in $G[T]$ to all but at most one vertex and hence $\deg_{G[T]}(v) \ge k+1$. Thus, $\alpha_k(G) \le k+2$ and we obtain $f(k,d) \le \frac{k+2}{d+k+1}$.\\
(5) Consider the graph $G = (K_{d+2}-E(K_3)) \cup q(K_{d+1}-E(K_3))$. Then $n(G) = (q+1) d + q+2$ and $d(G) n(G) = (d-1)(d+1)+3(d-1) + q((d-2)d + 3(d-2)) = (q+1)d^2+(q+3)d-(4+6q)$. Since $d \le 4+6q$, it follows that 
$$d(G) = \frac{(q+1)d^2+(q+3)d-(4+6q)}{(q+1)d+q+2} \le \frac{(q+1)d^2+(q+3)d-d}{(q+1)d+q+2} = d.$$ 
As clearly $\alpha_2(G) = 3(q+1)$, we obtain therefore, together with Theorem~\ref{main} (1), 
$$\frac{3}{d+3} \le f(2,d) \le \frac{3(q+1)}{(q+1)d+q+2} = \frac{3}{d+\frac{q+2}{q+1}} = \frac{3}{d+1+\frac{1}{q+1}}.$$ 
(6) Let $k \ge 2$ and consider the graph $G = (K_{k+3}-E(K_{k+1})) \cup k K_{1,k+1}$. Then $n(G) = k+3 + k(k+2) = k^2+3k+3$ and $d(G) n(G) = 2(k+2) + (k+1) 2 + 2k(k+1) = 2(k^2+3k+3) = 2 n(G)$. Hence, $d(G) = 2$. Moreover, it is easy to see that $\alpha_k(G)= (k+1)^2$. Thus this implies that
$$f(k,2) \le \frac{\alpha_k(G)}{n(G)} = \frac{(k+1)^2}{k^2+3k+3} = \frac{k+1}{k+2+\frac{1}{k+1}}.$$
Together with the bound from item(2) of Theorem~\ref{main}, we obtain
$$\frac{k}{k+1} \le f(k,2) \le \frac{k+1}{k+2+\frac{1}{k+1}}.$$
(7) By Theorem~\ref{thm_bol} there is an $r$-regular graph $H$ with $g(H) \ge k+4$ and $n = n(H) \ge \frac{2((r-1)^{k+3}-1)}{r-2}$. Take $n$ even and let $G = K_n - E(H)$. Then $d = d(G) = n-1-r$. Let $T \subseteq V(G)$ be a subset of $k+3$ vertices. As $g(H) \ge k+4$, $\overline{G}[T]$ is a forest and thus there is a vertex in $T$ which is adjacent in $G$ to all other vertices from $T$ with the exception of at most one. Hence, $T$ cannot be a $k$-independent set and thus $\alpha_k(G) \le k+2$. This implies that $f(k,d) \le \frac{\alpha_k(G)}{n} \le \frac{k+2}{d+r+1}$. 
As $d \sim 2r^{k+2}$, we have $r \sim (\frac{d}{2})^{\frac{1}{k+2}}$, and thus there is a constant $c > 0$ such that $r = c (\frac{d}{2})^{\frac{1}{k+2}}$, implying that $f(k,d) \le  \frac{k+2}{d+c(\frac{d}{2})^{\frac{1}{k+2}}+1}$.
\end{proof}


%%%%%%%%%%%%%%%%%%%% SECTION 5 %%%%%%%%%%%%%%%%%%%%

\section{Open problems}

We close this paper with the following open problems.


\begin{problem}
Is $f(k,d)$ in fact a minimum for every $k$ and $d$? Namely, does
$$\inf \left\{\frac{\alpha_k(G)}{n(G)} : G \mbox{ graph with } d(G) \le d \right\} = \min \left\{\frac{\alpha_k(G)}{n(G)} : G \mbox{ graph with } d(G) \le d\right\}$$
hold?
\end{problem}

In case the answer to this problem is positive, this may have several consequences in computing $f(k,d)$.

\begin{problem}
Is the bound $f(k,d) \ge \frac{2k+2-d}{2k+2}$ of Theorem~\ref{main} (2) sharp for $k \ge d \ge 2$?
\end{problem}

Below are the best possible bounds on $f(2,d)$ we have for $d = 0,1, \ldots, 10$.


\begin{center}
    \begin{tabular}{|c|c|c|c|c|}
        \hline
                &              lower          &        upper          &                                            & theorem used\\
        $d$ & bound$^*$  &   bound &  graph for upper bound &  for\\ 
                &&                     &                                   & upper bound \\ \hline 
        $0$ & $1$ & $1$ & $K_1$& -\\ \hline
        $1$ & $5/6$ & $5/6$ & $K_{1,k+1} \cup kK_1$& \ref{main}(2)\\ \hline
        $2$ & $2/3$ & $9/13$ & $(K_5 -E(K_3)) \cup 2K_{1,3}$& \ref{upper_bounds} (6)\\ \hline
        $3$ & $1/2$ & $3/5$ & $K_{5} - E(K_3)$& \ref{upper_bounds} (5), $q=0$\\ \hline
        $4$ & $4/9$ & $1/2$ & $K_{6} - E(K_3)$& \ref{upper_bounds} (5), $q=0$\\ \hline
        $5$ & $7/18$ & $6/13$ & $(K_{7} - E(K_3)) \cup (K_{6} - E(K_3))$& \ref{upper_bounds} (5), $q=1$\\ \hline
        $6$ & $1/3$ & $2/5$ & $(K_{8} - E(K_3)) \cup (K_{7} - E(K_3))$&  \ref{upper_bounds} (5), $q=1$\\ \hline
        $7$ & $11/36$ & $6/17$ & $(K_{9} - E(K_3)) \cup (K_{8} - E(K_3))$&  \ref{upper_bounds} (5), $q=1$\\ \hline
        $8$ & $5/18$ & $6/19$ & $(K_{10} - E(K_3)) \cup (K_{9} - E(K_3))$&  \ref{upper_bounds} (5), $q=1$\\ \hline
        $9$ & $1/4$ & $2/7$ & $(K_{11} - E(K_3)) \cup (K_{10} - E(K_3))$&  \ref{upper_bounds} (5), $q=1$\\ \hline
        $10$ & $7/30$ & $6/23$ & $(K_{12} - E(K_3)) \cup (K_{11} - E(K_3))$&  \ref{upper_bounds} (5), $q=1$\\ \hline
    \end{tabular}
    \end{center}
    \mbox{}\\[-3ex]
    \mbox{}
    \hspace{8ex}\small{*Lower bounds are from Thm.~\ref{main}(2) in case $d=1$ and Thm.~\ref{main}(1) else.}


\mbox{}
\begin{problem}
Improve upon the values given in the table.
\end{problem}



In order to better understand $f(k,d)$, we can define 
$$f(k,d,\Delta) = \inf \left\{\frac{\alpha_k(G)}{n(G)} : G \mbox{ is a graph with } d(G) \le d \mbox{ and } \Delta(G) \le \Delta\right\},$$
where $\Delta \ge d$, and $k$ are all nonnegative integers. Observe that $f(k,d) = \inf \{f(k,d,\Delta) : \Delta \ge d\}$ and hence a knowledge on $f(k,d,\Delta)$ may help in obtaining better bounds on $f(k,d)$. For instance, let us take $f(2,2,3)$. Observe that, from Theorem~\ref{main} (2), $f(2,2,3) \ge f(2,2) \ge \frac{2}{3}$. Further, consider the graph $G = R_8 \cup 4K_{1,3}$ on $24$ vertices, where $R_8$ is the graph depicted below (note that $R_8$ is the extremal graph for Reed's upper bound of $\frac{3}{8}n$ on the domination number for graphs on $n$ vertices with minimum degree at least $3$), and observe that $\alpha_2(G) = 17$, $n(G) = 24$ and $\Delta(G) = 3$. Then, it follows that $\frac{2}{3} \le f(2,2) \le f(2,2,3) \le \frac{17}{24}$. 

\begin{figure}[h]
\begin{center}
\psset{unit=0.7cm, linewidth=0.03cm}
   \begin{pspicture}(-5,-1)(8,3.5)
   \cnode*(1,0){0.15}{1}
   \cnode*(2,0){0.15}{2}
   \cnode*(3,1){0.15}{3}
   \cnode*(3,2){0.15}{4}
   \cnode*(2,3){0.15}{5}
   \cnode*(1,3){0.15}{6}
   \cnode*(0,2){0.15}{7}
   \cnode*(0,1){0.15}{8} 
   \ncline{1}{2}
   \ncline{2}{3}
   \ncline{3}{4}
   \ncline{4}{5}
   \ncline{5}{6}
   \ncline{6}{7}
   \ncline{7}{8}
   \ncline{8}{1}
   \ncline{1}{5}
   \ncline{2}{6}
   \ncline{3}{7}
   \ncline{4}{8}
   \put(0,-1){\small{The graph $R_8$.}}
   \end{pspicture}
   \end{center}
   \end{figure}

But if we consider for instance the graph $H= (K_5 -E(K_3)) \cup 2K_{1,3}$, then we have there $\alpha_2(H) = 9$, $n(H) = 13$ and $\Delta(H) = 4$ and thus $\frac{2}{3} \le f(2,2) \le f(2,2,4) \le \frac{9}{13}$, which is better than the bound $\frac{17}{24}$ obtained with the graph $G$. Thus, we would like to state the following question.

\begin{problem}
Obtain lower and upper bounds on $f(k,d, \Delta)$.
\end{problem}

\begin{thebibliography}{50}

\bibitem{AjKoSz1} M. Ajtai, J. Koml\'os, and E. Szemer\'edi.
\newblock A note on Ramsey numbers.
\newblock {\em J. Comb. Theory Ser. A}, 29:354--360, 1980.

\bibitem{AlKaSe} N. Alon, J. Kahn, P. D. Seymour. 
\newblock Large induced degenerate subgraphs.
\newblock {\em Graphs Combin.} 3(3):203--211, 1987.

\bibitem{AlSp} N. Alon and J.H. Spencer.
\newblock {\em The probabilistic method} (2nd ed.). 
\newblock Wiley, 2000.


\bibitem{BHHL} J.-C. Bermond, F. Havet, F. Huc, C. Linhares Sales
\newblock Improper coloring of weighted grid and hexagonal graphs.
\newblock {\em  Discrete Math. Algorithms Appl.} 2(3):395--411, 2010. 

\bibitem{BCFM} M. Blidia, M. Chellali, O. Favaron, N. Meddah. 
\newblock Maximal $k$-independent sets in graphs.
\newblock {\em Discuss. Math. Graph Theory} 28(1):151--163, 2008.

\bibitem{BCHN} A. Bojilov, Y. Caro, A. Hansberg, N. Nenov. 
\newblock Partitions of graphs into small and large sets.
 \newblock submitted.

\bibitem{Bol} B. Bollob\'as. 
\newblock {\em Extremal graph theory}, Reprint of the 1978 original.
\newblock Dover Publications, Inc., Mineola, NY, xx+488 pp, 2004.

\bibitem{BoMa} B. Bollob\'as, B. Manvel.
\newblock Optimal vertex partitions.
\newblock {\em Bull. London Math. Soc.}11(2):113--116, 1979. 

\bibitem{BoKoTo} O. V. Borodin, A. V. Kostochka, B. Toft.
\newblock Variable degeneracy: extensions of Brooks' and Gallai's theorems.
\newblock {\em Discrete Math.} 214(1-3):101--112, 2000. 

\bibitem{BGHR}  P. Borowiecki, F. G\"oring, J. Harant, D. Rautenbach.
 \newblock The potential of greed for independence.
  \newblock {\em J. Graph Theory} 71(3):245--259, 2012.

\bibitem{Caro} Y. Caro.
\newblock New results on the independence number.
\newblock {\em Tech. Report, Tel-Aviv University}, 1979.

\bibitem{CaTu}
Y. Caro, Z. Tuza.
\newblock Improved lower bounds on $k$-independence.
\newblock {\em J. Graph Theory} 15(1):99--107, 1991.

\bibitem{Cat1} P. A. Catlin.
\newblock Another bound on the chromatic number of a graph
\newblock {\em Discrete Math.} 24(1):1--6, 1978.

\bibitem{Cat2} P. A. Catlin.
\newblock Graph decompositions satisfying extremal degree constraints
\newblock {\em J. Graph Theory} 2(2):165--170, 1978. 

\bibitem{CFHV_survey} M. Chellali, O. Favaron, A. Hansberg, L. Volkmann.
\newblock $k$-domination and $k$-independence in graphs: a survey.
\newblock {\em Graphs Combin.} 28(1):1--55, 2012. 

\bibitem{CCW} L. J. Cowen, R. H.  Cowen, D. R. Woodall.
\newblock Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency.
 \newblock {\em J. Graph Theory} 10(2):187--195, 1986. 

\bibitem{CPS} B. Csaba, T. A. Plick, A. Shokoufandeh.
\newblock A note on the Caro-Tuza bound on the independence number of uniform hypergraphs.
 \newblock {\em Australas. J. Combin.} 52, 235--242, 2012. 

\bibitem{Faj} S. Fajtlowicz
\newblock On conjectures of Graffiti, III. 
 \newblock {\em Congr. Numer.} 66:23--32, 1988.

\bibitem{Fav} O. Favaron.
\newblock $k$-domination and $k$-independence in graphs.
 \newblock {\em Ars Combin.} 25(C):159--167, 1988.

\bibitem{FaMaSa} O. Favaron, M. Mah{\'e}o, J.F. Sacl\'e.
\newblock On the residue of a graph.
 \newblock {\em J. Graph Theory} 15:39--64, 1991.

\bibitem{FrHe} M. Frick, M. Henning.
\newblock Extremal results on defective colorings of graphs.
\newblock {\em Discrete Math.} 126(1-3):151--158, 1994. 

\bibitem{GHRSch} F. G\"oring, J. Harant, D. Rautenbach and I. Schiermeyer.
\newblock On $\mathcal{F}$-independence in graphs.
 \newblock {\em Discuss. Math. Graph Theory} 29(2):377--383, 2009.


\bibitem{Gri} J. R. Griggs.
\newblock Lower Bounds on the Independence Number in Terms of the Degrees.
\newblock {\em Journal of Combinatorial Theory, Series B} 34(1):22--39, 1983.


\bibitem{HaLa} M. M. Halld\'orsson and H. Ch. Lau.
\newblock Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring.
\newblock {\em Journal of Graph Algorithms and Applications} 1(3):49--61, 1997.

\bibitem{HaRa}  J. Harant, D. Rautenbach.
\newblock Independence in connected graphs
 \newblock {\em Discrete Appl. Math.} 159(1):79--86, 2011.

\bibitem{HaSch} J. Harant and I. Schiermeyer.
\newblock On the independence number of a graph in terms of order and size.
\newblock {\em Discrete Math.} 232:131--138, 2001.

\bibitem{HKS} F. Havet, R. J. Kang, J.-S. Sereni.
 \newblock Improper coloring of unit disk graphs.
 \newblock {\em Networks} 54(3):150--164, 2009. 

\bibitem{HS} G.\ Hopkins and W.\ Staton.
\newblock Vertex partition and $k$-small subsets of graphs.
\newblock {\em Ars Combin.} 22:19--24, 1986.

\bibitem{Jel} F. Jelen.
\newblock $k$-Independence and the $k$-residue of a graph.
  \newblock {\em J. Graph Theory} 32:241--249, 1999.

\bibitem{LiZa} Y. Li, W. Zang.
\newblock Differential methods for finding independent sets in hypergraphs.
\newblock {\em SIAM J. Discrete Math.} 20(1):96--104, 2006.

\bibitem{Los} E. Losievskaja.
\newblock Approximation algorithms for independent set problems on hypergraphs.
  Ph.D. thesis, Reykjav\'ik University, 2009, http://hdl.handle.net/1946/7410.

\bibitem{Lov} L. Lov\'asz. 
\newblock On decompositions of graphs.
\newblock {\em Studia Sci. Math Hungar.} 1:237--238, 1966.

\bibitem{Mur} O. Murphy.
\newblock Lower bounds on the stability number of graphs computed in terms of degrees.
\newblock {\em Discrete Math.} 90(2):201--211, 1991.

\bibitem{Rab} L. Rabern.
\newblock Partitioning and coloring with degree constraints.
\newblock  \arxiv{1202.5855v1}.

\bibitem{Sel} S.M. Selkow.
 \newblock The independence number of a graph in terms of degrees.
\newblock {\em  Discrete Math.} 132:363--365, 1994.

\bibitem{ShaSri} H. Shachnai, A. Srinivasan.
\newblock Finding large independent sets in graphs and hypergraphs. 
 \newblock {\em SIAM J. Discrete Math.} 18(3):488--500 (electronic), 2004/05.

\bibitem{Shea1} J.B. Shearer.
\newblock A note on the independence number of triangle-free graphs.
\newblock {\em  Discrete Math.} 46:83--87, 1983.

\bibitem{Shea2} J.B. Shearer.
\newblock A note on the independence number of triangle-free graphs. II.
 \newblock {\em J. Comb. Theory, Ser. B} 53:300--307, 1991.

\bibitem{Thi} T. Thiele.
\newblock A lower bound on the independence number of arbitrary hypergraphs. 
\newblock {\em J. Graph Theory} 30(3):213--221, 1999. 

\bibitem{Tur} P. Tur\'an.
\newblock An extremal problem in graph theory (hungarian).
\newblock {\em Mat Fiz Lapok} 48:436--452, 1941.

\bibitem{Wei} V. K. Wei.
\newblock A lower bound on the stability number of a simple graph.
 \newblock {\em Bell Laboratories Technical Memorandum}, 81--11217--9, Murray Hill, NJ, 1981.




\end{thebibliography}



\end{document}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
Thanks to Professor Querty for suggesting the proof of
Lemma~\ref{lem:Technical}.

