# A survey of the Hornich-Hlawka inequality

Dan-Ştefan Marinescu  National College ”Iancu de Hunedoara”, Hunedoara,
Romania<EMAIL_ADDRESS>and  Constantin P. Niculescu  Department of
Mathematics, University of Craiova, Craiova 200585, Romania
<EMAIL_ADDRESS>
(Date: June 30, 2024)

###### Abstract.

In this survey, we review the many faces of the Hornich-Hlawka inequality.
Several open problems that seem of utmost interest are mentioned.

###### Key words and phrases:

Hornich-Hlawka inequality, completely monotone function, invariant measure,
$L^{p}$ space, finite representability

###### 2000 Mathematics Subject Classification:

Primary 46B04, 46B20; Secondary 26D15

Corresponding author: Constantin P. Niculescu

##  1\. Introduction

The Hornich-Hlawka inequality, in its original form, asserts that

($HH$)
$\left\|\mathbf{x}\right\|_{2}+\left\|\mathbf{y}\right\|_{2}+\left\|\mathbf{z}\right\|_{2}+\left\|\mathbf{x}+\mathbf{y}+\mathbf{z}\right\|_{2}\geq\left\|\mathbf{x}+\mathbf{y}\right\|_{2}+\left\|\mathbf{y}+\mathbf{z}\right\|_{2}+\left\|\mathbf{z}+\mathbf{x}\right\|_{2}$

for every triplet $\mathbf{x},\mathbf{y},\mathbf{z}$ of vectors in the
Euclidean space $\mathbb{R}^{N}$ and thus in any Hilbert space, real or
complex. Here (and what follows), $\left\|\cdot\right\|_{2}$ denotes the
Hilbertian norm.

The story of this inequality started ca. 80 years ago, when H. Hornich [17]
mentioned it as a consequence of his main result. He referred to E. Hlawka for
a direct algebraic argument saying that _Für den Spezialfall_ $m=1$, $n=2$
_hat Herr HLAWKA mir einen rein algebraischen Beweis angegeben_ (in
translation: For the special case $m=1$, $n=2$, Mr. Hlawka gave me one purely
algebraic proof). Hlawka’s argument is both short and unexpected. It took into
account the identity,

($Fr$)
$\left\|\mathbf{x}\right\|_{2}^{2}+\left\|\mathbf{y}\right\|_{2}^{2}+\left\|\mathbf{z}\right\|_{2}^{2}+\left\|\mathbf{x}+\mathbf{y}+\mathbf{z}\right\|_{2}^{2}=\left\|\mathbf{x}+\mathbf{y}\right\|_{2}^{2}+\left\|\mathbf{y}+\mathbf{z}\right\|_{2}^{2}+\left\|\mathbf{z}+\mathbf{x}\right\|_{2}^{2},$

(used by M. Fréchet [14] to characterize the inner product spaces) to derive
the relation

$\left(\left\|\mathbf{x}\right\|_{2}+\left\|\mathbf{y}\right\|_{2}+\left\|\mathbf{z}\right\|_{2}+\left\|\mathbf{x}+\mathbf{y}+\mathbf{z}\right\|_{2}-\left\|\mathbf{x}+\mathbf{y}\right\|_{2}-\left\|\mathbf{y}+\mathbf{z}\right\|_{2}-\left\|\mathbf{z}+\mathbf{x}\right\|_{2}\right)\\\
\times\left(\left\|\mathbf{x}\right\|_{2}+\left\|\mathbf{y}\right\|_{2}+\left\|\mathbf{z}\right\|_{2}+\left\|\mathbf{x}+\mathbf{y}+\mathbf{z}\right\|_{2}\right)\\\
=(\left\|\mathbf{x}\right\|_{2}+\left\|\mathbf{y}\right\|_{2}-\left\|\mathbf{x}+\mathbf{y}\right\|_{2})\left(\left\|\mathbf{z}\right\|_{2}+\left\|\mathbf{x}+\mathbf{y}+\mathbf{z}\right\|_{2}-\left\|\mathbf{x}+\mathbf{y}\right\|_{2}\right)\\\
+(\left\|\mathbf{y}\right\|_{2}+\left\|\mathbf{z}\right\|_{2}-\left\|\mathbf{y}+\mathbf{z}\right\|_{2})\left(\left\|\mathbf{x}\right\|_{2}+\left\|\mathbf{x}+\mathbf{y}+\mathbf{z}\right\|_{2}-\left\|\mathbf{y}+\mathbf{z}\right\|_{2}\right)\\\
+(\left\|\mathbf{z}\right\|_{2}+\left\|\mathbf{x}\right\|_{2}-\left\|\mathbf{z}+\mathbf{x}\right\|_{2})\left(\left\|\mathbf{y}\right\|_{2}+\left\|\mathbf{x}+\mathbf{y}+\mathbf{z}\right\|_{2}-\left\|\mathbf{z}+\mathbf{x}\right\|_{2}\right).$

The proof ends by noticing that the right hand side is nonnegative due to the
triangle inequality.

The weighted form of the Hornich-Hlawka’s inequality is a direct consequence
of the unweighted form $(HH):$

$\frac{\lambda\left\|\mathbf{x}\right\|_{2}+\mu\left\|\mathbf{y}\right\|_{2}+\nu\left\|\mathbf{z}\right\|_{2}}{\lambda+\mu+\nu}+\left\|\frac{\lambda\mathbf{x}+\mu\mathbf{y}+\nu\mathbf{z}}{\lambda+\mu+\nu}\right\|_{2}\\\
\geq\frac{1}{\lambda+\mu+\nu}\left[\left\|\lambda\mathbf{x}+\mu\mathbf{y}\right\|_{2}+\left\|\mu\mathbf{y}+\nu\mathbf{z}\right\|_{2}+\left\|\nu\mathbf{z}+\lambda\mathbf{x}\right\|_{2}\right]\\\
=\frac{1}{\lambda+\mu+\nu}\left[\left(\lambda+\mu\right)\left\|\frac{\lambda\mathbf{x}+\mu\mathbf{y}}{\lambda+\mu}\right\|_{2}\right.\\\
\left.+\left(\mu+\nu\right)\left\|\frac{\mu\mathbf{y}+\nu\mathbf{z}}{\mu+\nu}\right\|_{2}+\left(\nu+\lambda\right)\left\|\frac{\nu\mathbf{z}+\lambda\mathbf{x}}{\nu+\lambda}\right\|_{2}\right],$

for all $\mathbf{x},\mathbf{y},\mathbf{z\in}\mathbb{R}^{N}$ and all scalars
$\lambda,\mu,\nu>0.$

D. M. Smiley and M. F. Smiley [51] (as well as A. Simon and P. Volkmann [50])
used the terminology of _quadrilateral space_ for what we call here a Hornich-
Hlawka space. A simple geometric argument for their terminology is offered by
the solution of R. Tauraso to the problem [13]. He proved that in the
Euclidean plane this inequality is equivalent to the following property of the
quadrilaterals (convex or not): _Let_ $ABCD$ _be a quadrilateral_ , $E$ _the
midpoint of_ $AC$, _and_ $F$ _the midpoint of_ $BD$. _Then_

$\left\|AB\right\|_{2}+\left\|BC\right\|_{2}+\left\|CD\right\|_{2}+\left\|DA\right\|_{2}\geq\left\|AC\right\|_{2}+\left\|BD\right\|_{2}+2\left\|EF\right\|_{2}.$

The proof extends verbatim to all Euclidean spaces $\mathbb{R}^{N}$ with
$N\geq 2.$ Even more, according to Remark 1, in the 2-dimensional case, the
Euclidean norm can be replaced by any other norm on $\mathbb{R}^{2}.$

For the full information of our readers, we have included some information
about the lives and achievements of Hornich and Hlawka in the Bibliography
section. See [61] and [55].

Stigler’s law of eponymy states that no scientific discovery is named after
its original discoverer and the case of this inequality is not an exception.
Indeed, some authors ([25], [45]) refer to (HH) as the _Hornich-Hlawka
inequality_ , while others ([33], [34] [52], [57]) to the _Hlawka inequality._
We adopt here the first variant, which seems better motivated. No matter how
we refer to the inequality (HH), a fact is certain: this is a perennial
subject which continue to attract a great deal of attention and our paper is
aimed to emphasize the mathematics around it. To do this we survey the known
results and point out the wealth of rather important open problems that are
out there, at least some of which should be fairly elementary for someone with
the right background.

##  2\. Hornich-Hlawka inequality by transfer from an $L^{1}$ space

Looking at the aforementioned proof of the (HH) inequality, the reader will
inevitably react as G. Pólya noted in the Preface of his influential book How
to Solve It : _Yes, the solution seems to work, it appears to be correct. But
how is it possible to invent such a solution?_ See [41], p. vi.

Many norm inequalities in real analysis follow from appropriate inequalities
for real numbers by integration, after substituting the real variables with
integrable functions. Think for example at the standard proof of Hölder’s
inequality, which appears as a consequence of Young’s inequality. See [37], p.
13.

Surprisingly, the same recipe works in the case of Hornich-Hlawka inequality.
Indeed, by taking into account the inequality

(2.1) $|x|+|y|+|z|+|x+y+z|\geq|x+y|+|y+z|+|z+x|\text{\quad for all
}x,y,z\in\mathbb{R},$

which is an easy consequence of the ordering properties of $\mathbb{R},$ one
can easily prove the Hornich-Hlawka inequality not only in the case of Hilbert
spaces but also for a large variety of spaces. Notice also that the inequality
2.1 plays a central role in the original proof of Popoviciu’s inequality. See
[43].

For convenience, we will call a (real or complex) Banach space
$E=(E,\left\|\cdot\right\|)$ a _Hornich-Hlawka space_ if its norm verifies the
inequality

(2.2)
$\left\|\mathbf{x}\right\|+\left\|\mathbf{y}\right\|+\left\|\mathbf{z}\right\|+\left\|\mathbf{x}+\mathbf{y}+\mathbf{z}\right\|\geq\left\|\mathbf{x}+\mathbf{y}\right\|+\left\|\mathbf{y}+\mathbf{z}\right\|+\left\|\mathbf{z}+\mathbf{x}\right\|$

for every triplet of elements $\mathbf{x},\mathbf{y},\mathbf{z}$ of $E.$

An easy but important remark is the membership of every $L^{1}$ space to this
class of Banach spaces. The next result refers to the more sophisticated case
of (Bochner integrable) vector-valued functions. See the book of Diestel and
Uhl [7], Chapter II, Section 2, for a quick introduction to this theory of
integration.

######  Lemma 1.

Let $E$ be a Hornich-Hlawka space and $(\Omega,\Sigma,\mu)$ a measure space.
Then the Banach space $L_{E}^{1}(\Omega,\Sigma,\mu),$ of all Bochner
integrable functions $f:\Omega\rightarrow E$ with respect to $\mu,$ is also a
Hornich-Hlawka space.

In particular, every space
$L^{1}(\Omega,\Sigma,\mu)=L_{\mathbb{R}}^{1}(\Omega,\Sigma,\mu)$ is Hornich-
Hlawka.

###### Proof.

Indeed, for every triplet of functions $\mathbf{f},\mathbf{g},\mathbf{h}\in
L_{E}^{1}(\Omega,\Sigma,\mu),$

$\left\|\mathbf{f}(\omega)\right\|+\left\|\mathbf{g}(\omega)\right\|+\left\|\mathbf{h}(\omega)\right\|+\left\|\mathbf{f}(\omega)+\mathbf{g}(\omega)+\mathbf{h}(\omega)\right\|\\\
\geq\left\|\mathbf{f}(\omega)+\mathbf{g}(\omega)\right\|+\left\|\mathbf{g}(\omega)+\mathbf{h}(\omega)\right\|+\left\|\mathbf{h}(\omega)+\mathbf{f}(\omega)\right\|\text{\quad}$

for all $\omega\in\Omega,$ whence by integration we obtain

$\int_{\Omega}\left\|\mathbf{f}(\omega)\right\|\mathrm{d}\mu+\int_{\Omega}\left\|\mathbf{g}(\omega)\right\|\mathrm{d}\mu+\int_{\Omega}\left\|\mathbf{h}(\omega)\right\|\mathrm{d}\mu+\int_{\Omega}\left\|\mathbf{f}(\omega)+\mathbf{g}(\omega)+\mathbf{h}(\omega)\right\|\mathrm{d}\mu\\\
\geq\int_{\Omega}\left\|\mathbf{f}(\omega)+\mathbf{g}(\omega)\right\|\mathrm{d}\mu+\int_{\Omega}\left\|\mathbf{g}(\omega)+\mathbf{h}(\omega)\right\|\mathrm{d}\mu+\int_{\Omega}\left\|\mathbf{h}(\omega)+\mathbf{f}(\omega)\right\|\mathrm{d}\mu.$

that is,

$\left\|\mathbf{f}\right\|_{L_{E}^{1}}+\left\|\mathbf{g}\right\|_{L_{E}^{1}}+\left\|\mathbf{h}\right\|_{L_{E}^{1}}+\left\|\mathbf{f}+\mathbf{g}+\mathbf{h}\right\|_{L_{E}^{1}}\geq\left\|\mathbf{f}+\mathbf{g}\right\|_{L_{E}^{1}}+\left\|\mathbf{g}+\mathbf{h}\right\|_{L_{E}^{1}}+\left\|\mathbf{h}+\mathbf{f}\right\|_{L_{E}^{1}}.$

∎

######  Corollary 1.

Under the hypotheses of Lemma _1_ , every Banach space that embeds linearly
and isometrically into a space $L_{E}^{1}(\Omega,\Sigma,\mu)$ is a Hornich-
Hlawka space.

The original Hornich-Hlawka inequality can be derived from Corollary 1 by
noticing that the Euclidean space $\mathbb{R}^{N}$ embeds linearly and
isometrically into the Lebesgue space $L^{1}(S^{N-1}),$ associated to the
normalized Haar measure $m$ on the unit sphere $S^{N-1}$ of $\mathbb{R}^{N},$
invariant to rotations. The embedding $\Phi:\mathbb{R}^{N}\rightarrow
L^{1}(S^{N-1})$ is defined via the formula

$\Phi(\mathbf{u})=\langle\mathbf{u},\cdot\rangle.$

To check this, let $\mathbf{u}_{0}\in S^{N-1}$ arbitrarily fixed and put

$C=\left\|\Phi(\mathbf{u}_{0})\right\|_{L^{1}}=\int_{S^{N-1}}\left|\langle\mathbf{u}_{0},\mathbf{x}\rangle\right|\mathrm{d}m.$

By rotational invariance,
$C=\int_{S^{N-1}}\left|\langle\mathbf{u},\mathbf{x}\rangle\right|\mathrm{d}m$
for all $\mathbf{u}\in S^{N-1}$, whence

$\left\|\Phi(\mathbf{u})\right\|_{L^{1}}=\left\|\mathbf{u}\right\|_{2}\text{\quad
for all }\mathbf{u\in}\mathbb{R}^{N}.$

This way the validity of the Hornich-Hlawka inequality is obtained by
”transfer” from the case $L^{1}$ space. We will come back to the idea of using
the Haar measures for deriving Hornich-Hlawka type inequalities in Section 6.

As noticed H. S. Witsenhausen [60], the embeddability in an $L^{1}$ space is
equivalent to the property

$\sum_{i,j=1}^{n}w_{i}w_{j}\left\|\mathbf{x}_{i}-\mathbf{x}_{j}\right\|\leq
0,$

for $w_{i}$ integers of sum 1, any $n$ and any $n$ points $\mathbf{x}_{k}.$

In the next section we will show that all spaces $L^{p}\left([0,1]\right)$
with $p\in(1,2)$ can be embedded into an $L^{1}$ space.

##  3\. The Levy transfer theorem

Recall that any $L^{p}$ space is associated to a measure space
$(\Omega,\Sigma,\mu)$ and consists of all (equivalence classes) of measurable
functions on $\Omega$ such that

$\left\|f\right\|_{p}=\left(\int_{\Omega}\left|f\right|^{p}d\mu\right)^{1/p}<\infty\text{\quad
for }0<p<\infty$

and

$\left\|f\right\|_{\infty}=\inf\left\\{C>0:\left|f(\omega)\right|\leq C\text{
for almost every }\omega\right\\}<\infty\text{\quad for }p=\infty.$

A characterization of the finite-dimensional Banach spaces that can be
embedded in an $L^{P}$ space with $p\in(0,\infty),$ was found by P. Levy (see
[26], § 63) in connection with his work on the theory of stable processes.

######  Theorem 1.

An $N$-dimensional real Banach space $E=(\mathbb{R}^{N},\left\|\cdot\right\|)$
embeds isometrically in $L^{p}(0,1)$ $(p>0)$ if and only if there exists a
finite Borel measure $\mu$ on the unit sphere $S^{N-1}$ in $\mathbb{R}^{N}$ so
that, for every $x\in E,$

$\left\|x\right\|^{p}=\int_{\Omega}\left|\langle
x,\xi\rangle\right|^{p}d\mu(\xi).$

The last formula is called by A. Koldobsky [24] the _Blaschke-Levy
representation_. See [23], Theorem 2, for a generalization. For $p\in(0,2],$
this representation exists if and only if the function
$\exp(-\left\|x\right\|^{p})$ is positive definite and, hence, it is the
characteristic function of a symmetric stable measure in $\mathbb{R}^{N}.$

The work of P. Levy [26], I. J. Schoenberg [47], M. Kadets [20], C. Herz [16]
and J. Bretagnolle, D. Dacunha-Castelle and J. L. Krivine [3] have prove the
existence of the isometric embeddings of the real spaces
$\ell^{q}(N),~{}\ell^{q}$ and $L^{q}(0,1)$ in $L^{p}(0,1)$ for $0<p\leq q\leq
2.$ Here $\ell^{q}(N)$ is the the space $\mathbb{R}^{N}$ endowed with the norm

$\left\|\mathbf{x}\right\|_{q}=(\left|x_{1}\right|^{q}+\cdots+\left|x_{N}\right|^{q})^{1/q}$

and $\ell^{q}$ denotes its sequence space analogue.

Every separable real Hilbert space is isometric to a subspace of $L^{p}(0,1),$
whenever $p>0$. See J. Lindenstrauss and A. Pełczyński [29], Corollary 1, p.
312.

######  Remark 1.

Every $2$-dimensional real Banach space is isometric to a subspace of
$L^{1}(0,1).$ This was proved independently by C. Herz _[15]_, Th. S. Ferguson
_[11]_ and J. Lindenstrauss _[28]_. As a consequence, the Hornich-Hlawka
inequality _(HH)_ works for all $2$-dimensional real Banach spaces.

######  Remark 2.

L. Dor has shown that $\ell^{p}(3)$ is not isometric to any subspace of
$L^{1}(0,1)$ if $p>2.$ See _[9]_, Corollary of Theorem $1.5$, p. $265$.
Combined with the discussion above, it follows that none of the spaces
$L^{p}(0,1)$ and $\ell^{p}$ with $p>2$ can be isometrically embedded into a
space $L^{1}(0,1).$

The Hornich-Hlawka inequality has a finite dimensional character. It concerns
_only_ the 3-dimensional subspaces of a Banach space. As was noticed by A.
Neyman [35] (Corollary 3.4) there is no finite list of inequalities that
characterizes embeddability, neither in $L^{1}(0,1)$ nor in any other $L^{p}$
space unless $p=2$. This is accomplished by proving that for every $1\leq
p<\infty$, $p\neq 2$, and every $k\geq 2$ there is a $(k+1)$-dimensional
normed space that is not embeddable in $L^{p}$ and all of its $k$-dimensional
subspaces are embeddable in $L^{p}.$ A consequence is the following result:

######  Theorem 2.

There exist finite dimensional Hornich-Hlawka spaces that cannot be embedded
isometrically in $L^{1}(0,1).$

It is straightforward that none of the spaces $\ell^{p}(3)$ $(\mathbb{R}^{3}$
with the norm of index $p)$ for $p\in(\left(\log 3\right)/\left(\log 3-\log
2\right),\infty]$ is Hornich-Hlawka. For, check the inequality for
$\mathbf{x}=(-1,1,1)$, $\mathbf{y}=(1,-1,1)$ and $\mathbf{z}=(1,1,-1).$ Notice
that $\left(\log 3\right)/\left(\log 3-\log 2\right)=\allowbreak
2.\,\allowbreak 709\,511\,291...$ .

As a consequence, all spaces $L^{p}(0,1)$ with $p$ in the same range of values
fail to be Hornich-Hlawka. Even more, it seems very likely that the answer to
the following problem is positive.

######  Problem 1.

Prove that actually none of the spaces $\ell^{p}(3)$ with $p\in(2,\infty]$ is
Hornich-Hlawka.

A positive answer to Problem 1 would implies that none of the spaces
$L^{p}(0,1)$ with $p\in(2,\infty]$ is Hornich-Hlawka.

How apart can be the class of Hornich-Hlawka spaces from the rest of Banach
spaces?

######  Problem 2.

Are there Banach spaces whose all finite dimensional subspaces of dimension
greater than or equal to $3$ are not Hornich-Hlawka?

A positive solution to Problem 2, if it exists, will probably be an
amalgamation of the spaces $\ell^{3}(3),\ell^{4}(3),\ell^{5}(3),\ldots$ but we
lack a clear argument.

A natural generalization of $L^{p}$ spaces is provided by the class of
$L^{p(\cdot)}$ spaces _with variable exponent_. They differ from the classical
$L^{p}$ spaces in that the exponent $p$ is not constant but a function from
the measure space under attention to $[1,\infty]$. See the monograph of L.
Diening, P. Harjulehto, P. Hästö and M. Ruzicka [6] for a thorough
presentation.

######  Problem 3.

Is every $L^{p(\cdot)}(0,1)$ space with a variable exponent
$p(\cdot):(0,1)\rightarrow[1,2]$ a Hornich-Hlawka space?

Let $p\in[1,\infty)$ and $k\geq 1.$ The Sobolev space $W^{k,p}(0,1)$ consists
of all functions $u\in L^{p}\left(0,1\right)$ which admit weak derivatives
$\partial_{\alpha}u\in L^{p}\left(0,1\right)$ for all multi indices $\alpha$
with $\left|\alpha\right|\,\leq k.$ This is a Banach space with respect to the
norm

$\left\|u\right\|_{W^{k,p}}=\left(\sum\nolimits_{\left|\alpha\right|\,\leq
k}\int_{0}^{1}\left|\partial_{\alpha}\right|^{p}\mathrm{d}x\right)^{1/p}.$

A nice overview of the theory of Sobolev spaces is offered by the book of M.
Willem [58].

######  Theorem 3.

Let $k$ be a positive integer and $p\in[1,2].$ Then the spaces $W^{k,p}(0,1)$
and $W_{0}^{k,p}(0,1)$ $($the closure in $W^{k,p}(0,1)$ of the space of
infinitely differentiable functions compactly supported in $\Omega),$ both are
Hornich-Hlawka.

###### Proof.

Since $L^{p}(0,1)$ embeds linearly and isometrically into $L^{1}(0,1),$ it
follows that a similar result works for the pair of spaces
$L_{\mathbb{R}^{m}}^{p}(0,1)$ and $L_{\mathbb{R}^{m}}^{1}(0,1).$ According to
Lemma 1, this shows that $L_{\mathbb{R}^{m}}^{p}(0,1)$ is Hornich-Hlawka. The
map

$\Phi:W^{k,p}(0,1)\rightarrow L^{p}((0,1);\mathbb{R}^{m}),\text{
}\Phi(u)=\left(\partial^{\alpha}u\right)_{\left|\alpha\right|\leq k}$

is a linear isometry since
$\left\|\Phi(u)\right\|_{p}=\left\|u\right\|_{k,p}.$ Therefore $W^{k,p}(0,1)$
and its closed subspace $W_{0}^{k,p}(0,1)$ both are Hornich-Hlawka. ∎

The aforementioned monograph of Diening, Harjulehto, Hästö and Ruzicka [6]
also includes a comprehensive presentation of the theory of Sobolev spaces
$W^{k,p(\cdot)}(0,1)$ of a variable exponent. Related to Problem 3 is the
following question.

######  Problem 4.

Which Sobolev spaces $W^{k,p(\cdot)}(0,1)$ with a variable exponent
$p(\cdot):(0,1)\rightarrow[1,2]$ verify the Hornich-Hlawka inequality?

##  4\. The Hornich-Hlawka inequality through finite representability

The embeddability condition in Theorem 1 can be relaxed using the concepts of
finite representability and of isomorphic embedding.

A Banach space $X$ is said to be _finitely representable_ in a Banach space
$Y$ if for every $\varepsilon>0$ and every subspace $M$ of $X$ there exists a
finite dimensional subspace $N$ of $Y$ and a linear isomorphism
$T:M\rightarrow N$ such that

$(1-\varepsilon)\left\|x\right\|\leq\left\|T(x)\right\|\leq(1+\varepsilon)\left\|x\right\|\text{\quad
for all }x\in M.$

According to a famous result due to Dvoretzky, $\ell^{2}$ is finitely
representable in any Banach space. See Figiel [12] for a short proof.

On the other hand, according to the principle of local reflexivity (see [30]),
the second dual of any Banach space $X$ is finitely representable in $X$.

The following transfer theorem originates from Proposition 7.6 in [29]:

######  Theorem 4.

Suppose that $A=(a_{ik})_{i,k}$ is a real $m\times r$ matrix,
$B=(b_{jk})_{j,k}$ is a real $n\times r$ matrix and $(\lambda_{i})_{i=1}^{m}$
and $(\mu_{j})_{j=1}^{n}$ are two families of positive numbers. If for some
$p>0,$

$\sum\nolimits_{i=1}^{m}\lambda_{i}\left|\sum\nolimits_{k=1}^{r}a_{ik}t_{k}\right|^{p}\leq\sum\nolimits_{j=1}^{n}\mu_{j}\left|\sum\nolimits_{k=1}^{r}b_{jk}t_{k}\right|^{p}$

for all $t_{1},...,t_{r}\in\mathbb{R},$ then

$\sum\nolimits_{i=1}^{m}\lambda_{i}\left\|\sum\nolimits_{k=1}^{r}a_{ik}\mathbf{x}_{k}\right\|_{X}^{p}\leq\sum\nolimits_{j=1}^{n}\mu_{j}\left\|\sum\nolimits_{k=1}^{r}b_{jk}\mathbf{x}_{k}\right\|_{X}^{p}$

for every family $\mathbf{x}_{1},...,\mathbf{x}_{r}$ of vectors in a Banach
space $X=(X,\left\|\cdot\right\|_{X})$ which is finitely representable in
$L^{p}(0,1).$

###### Proof.

Indeed, we may reduce ourselves to the case where $X$ is finite dimensional
and for every $\varepsilon>0$ there exists a linear map $T:X\rightarrow
L^{p}(0,1)$ such that

$(1-\varepsilon)\left\|x\right\|^{p}\leq\left\|T(x)\right\|^{p}\leq(1+\varepsilon)\left\|x\right\|^{p}$

for all $x\in X.$ According to our hypothesis,

$\sum\nolimits_{i=1}^{m}\lambda_{i}\left|\langle\sum\nolimits_{k=1}^{r}a_{ik}\mathbf{x}_{k},\mathbf{u}\rangle\right|^{p}\leq\sum\nolimits_{j=1}^{n}\mu_{j}\left|\langle\sum\nolimits_{k=1}^{r}b_{jk}\mathbf{x}_{k},\mathbf{u}\rangle\right|^{p},$

for every $\mathbf{u}\in S^{N-1},$ and an appeal to Theorem 1 easily yields
the existence of a finite Borel measure $\mu$ on the unit sphere $S^{N-1}$ in
$\mathbb{R}^{N}$ such that

$(1-\varepsilon)\sum\nolimits_{i=1}^{m}\lambda_{i}\left\|\sum\nolimits_{k=1}^{r}a_{ik}\mathbf{x}_{k}\right\|_{X}^{p}\leq\sum\nolimits_{i=1}^{m}\lambda_{i}\left\|\sum\nolimits_{k=1}^{r}a_{ik}\mathbf{x}_{k}\right\|_{p}^{p}\\\
=\sum\nolimits_{i=1}^{m}\lambda_{i}\int_{S^{N-1}}\left|\langle\sum\nolimits_{j=1}^{r}a_{ij}\mathbf{x}_{j},\mathbf{u}\rangle\right|^{p}d\mu(\mathbf{u})\\\
\leq\sum\nolimits_{j=1}^{n}\mu_{j}\int_{S^{N-1}}\left|\langle\sum\nolimits_{k=1}^{r}b_{jk}\mathbf{x}_{k},\mathbf{u}\rangle\right|^{p}d\mu(\mathbf{u})\\\
=\sum\nolimits_{j=1}^{n}\mu_{j}\left\|\sum\nolimits_{k=1}^{r}b_{jk}\mathbf{x}_{k}\right\|_{p}^{p}\leq(1+\varepsilon)\sum\nolimits_{j=1}^{n}\mu_{j}\left\|\sum\nolimits_{k=1}^{r}b_{jk}\mathbf{x}_{k}\right\|_{X}^{p}.$

The proof ends by noticing that $\varepsilon>0$ was arbitrarily fixed. ∎

Theorem 4 implies the following new generalization of Hlawka’s inequality:

$\left\|\mathbf{x}\right\|_{X}^{p}+\left\|\mathbf{y}\right\|_{X}^{p}+\left\|\mathbf{z}\right\|_{X}^{p}+\left\|\mathbf{x}+\mathbf{y}+\mathbf{z}\right\|_{X}^{p}\geq\left\|\mathbf{x}+\mathbf{y}\right\|_{X}^{p}+\left\|\mathbf{y}+\mathbf{z}\right\|_{X}^{p}+\left\|\mathbf{z}+\mathbf{x}\right\|_{X}^{p}$

for all vectors in a Banach space $X=(X,\left\|\cdot\right\|_{X})$ which is
finitely representable in a space $L^{p}(0,1)$ with $0<p\leq 2.$

##  5\. The Hornich-Hlawka inequality in uniformly non-square spaces

In connection with the famous work [19] of Jordan and von Neumann concerning
the inner product spaces, J. A. Clarkson [4] has introduced the von Neumann-
Jordan constant $C_{NJ}(X)$ of a Banach space $X$ as

$C_{NJ}(X)=\sup\left\\{\frac{\left\|\mathbf{x}+\mathbf{y}\right\|^{2}+\left\|\mathbf{x}-\mathbf{y}\right\|^{2}}{2\left\|\mathbf{x}\right\|^{2}+2\left\|\mathbf{y}\right\|^{2}}:\mathbf{x},\mathbf{y}\in
X\text{ and }\left\|\mathbf{x}\right\|+\left\|\mathbf{y}\right\|\neq
0\right\\}.$

We have $1\leq C_{NJ}(X)\leq 2$ for all Banach spaces $X$ and $C_{NJ}(X)=1$
_if and only if_ $X$ _is a Hilbert space_. Notice also that $C_{NJ}(X)<2$ for
any uniformly convex space and $C_{NJ}(X)=2$ in the case of spaces
$L^{p}(\mathbb{R})$ with $p=1$ or $p=\infty$ and the same is true in the case
of Banach spaces of continuous functions endowed with the sup norm.

For details see [21] and [22].

######  Theorem 5.

In any Banach space,

$C_{NJ}(X)\left(\left\|x+y+z\right\|^{2}+\left\|x\right\|^{2}+\left\|y\right\|^{2}+\left\|z\right\|^{2}\right)\geq\left\|x+y\right\|^{2}+\left\|y+z\right\|^{2}+\left\|z+x\right\|^{2}.$

Notice that in the case of Hilbert spaces this inequality reduces to the
Hornich-Hlawka inequality.

###### Proof.

Indeed,

$C_{NJ}(X)\left(\left\|\mathbf{x}+y+z\right\|^{2}+\left\|x\right\|^{2}\right)\geq\frac{1}{2}\left\|2x+y+z\right\|^{2}+\frac{1}{2}\left\|y+z\right\|^{2}$

and

$C_{NJ}(X)\left(\left\|y\right\|^{2}+\left\|z\right\|^{2}\right)\geq\frac{1}{2}\left\|y+z\right\|^{2}+\frac{1}{2}\left\|y-z\right\|^{2}.$

On the other hand,

$\displaystyle\frac{1}{2}\left\|2x+y+z\right\|^{2}+\frac{1}{2}\left\|y-z\right\|^{2}$
$\displaystyle=\frac{1}{2}\left\|\left(x+y\right)+\left(x+z\right)\right\|^{2}+\frac{1}{2}\left\|\left(x+y\right)-(x+z)\right\|^{2}$
$\displaystyle\geq\left\|x+y\right\|^{2}+\left\|x+z\right\|^{2}.$

Therefore

$C_{NJ}(X)\left(\left\|x+y+z\right\|^{2}+\left\|x\right\|^{2}+\left\|y\right\|^{2}+\left\|z\right\|^{2}\right)\geq\left\|x+y\right\|^{2}+\left\|y+z\right\|^{2}+\left\|z+x\right\|^{2}.$

∎

A Banach space $X$ is called _uniformly non-square_ $($James _[18]_$)$ if
there exists a $\delta$ $\in(0,1)$ such that for any $x$, $y$ in the unit
sphere of $X$ either $\left\|\mathbf{x}+\mathbf{y}\right\|/2\leq 1-\delta$ or
$\left\|\mathbf{x}-\mathbf{y}\right\|/2\leq 1-\delta$.

The constant

$J(X)=\sup\\{\min(\left\|\mathbf{x}+\mathbf{y}\right\|,\left\|\mathbf{x}-\mathbf{y}\right\|):\left\|\mathbf{x}\right\|=\left\|\mathbf{y}\right\|=1\\}$

is called the _non-square_ or _James constant_ of $X$.

If $\dim X\geq 2,$ then $\sqrt{2}\leq J(X)\leq 2$ and $J(X)=\sqrt{2}$ if $X$
is a Hilbert space. A Banach space $X$ is uniformly non-square if and only if
$J(X)<2.$ According to M. Kato, L. Maligranda, and Y. Takahashi _[21]_,
Theorem $3$,

$\frac{1}{2}J(X)^{2}\leq
C_{NJ}(X)\leq\frac{J(X)^{2}}{\left(J(X)-1\right)^{2}+1},$

so the condition $C_{NJ}(X)<2$ is equivalent to the fact that $X$ is uniformly
non-square; see _[21]_, Proposition 1. As was noticed by James _[18]_, any
uniformly non-square space is reflexive.

The following Hornich-Hlawka type inequality that works in any Banach space
can be found in the paper by Y. Takahashi, S. E. Takahashi, and S. Wada [53]:

######  Theorem 6.

Let $E$ be a Banach space and $r,s\geq 1$ be two real numbers. Then

$\left(\left\|\mathbf{x}+\mathbf{y}\right\|^{s}+\left\|\mathbf{y}+\mathbf{z}\right\|^{s}+\left\|\mathbf{z}+\mathbf{x}\right\|^{s}\right)^{1/s}\\\
\leq
2^{1-\left(2/r\right)}3^{1/s}\left(\left\|\mathbf{x}\right\|^{r}+\left\|\mathbf{y}\right\|^{r}+\left\|\mathbf{z}\right\|^{r}+\left\|\mathbf{x}+\mathbf{y}+\mathbf{z}\right\|^{r}\right)^{1/r}$

for all $\mathbf{x,y},\mathbf{z}\in E.$

##  6\. Levi’s reduction theorem

F. W. Levi [25] found in 1949 a class of numerical inequalities that generates
vector inequalities simply by replacing the real variables with vectors in an
arbitrary Euclidean space and the absolute value with the Euclidean norm. His
result is based on the following lemma.

######  Lemma 2.

$(a)$ Let $\Phi:\mathbb{R}^{N}\times S^{N-1}\rightarrow\mathbb{R}$ be a
continuous function whose restriction to $S^{N-1}\times S^{N-1}$ is invariant
under the action of the special orthogonal group SO$(N),$ that is,

$\Phi\left(S\mathbf{y},S\mathbf{x}\right)=\Phi(\mathbf{y},\mathbf{x})$

for all $\mathbf{y},\mathbf{x}\in S^{N-1}$ and all orthogonal matrices $S$ of
determinant $1$ and dimension $N\times N.$ Then the integral

$I(\mathbf{y})=\int_{S^{N-1}}\Phi(\mathbf{y},\mathbf{x})d\sigma(\mathbf{x}),\text{\quad}\mathbf{y}\in\mathbb{R}^{N},$

is constant on $S^{N-1}$.

$(b)$ Suppose in addition that $\Phi$ also verifies the following condition of
homogeneity:

$\Phi(\lambda\mathbf{y},\mathbf{x})=\varphi(\lambda)\Phi(\mathbf{y},\mathbf{x})$

for a certain continuous function $\varphi:[0,\infty)\rightarrow\mathbb{R}$
and all $\lambda\in\mathbb{R}_{+},$ $\mathbf{y}\in\mathbb{R}^{N}$ and
$\mathbf{x}\in S^{N-1}.$ Then

$I(y)=\int_{S^{N-1}}\Phi(\mathbf{y},\mathbf{x})d\sigma(\mathbf{x})=C(\Phi)\cdot\varphi(\left\|\mathbf{y}\right\|_{2})\quad\text{for
all }y\in\mathbb{R}^{N},$

where $C(\Phi)$ is the value of constancy of $I(\mathbf{y})$ on $S^{N-1}$.

###### Proof.

The constancy of $I(\mathbf{y})$ on $S^{N-1}$ is a consequence of the fact
that SO$(N)$ acts transitively on $S^{N-1}$ and the measure $d\sigma$ is
invariant under the action of this group. The assertion $(b)$ is
straightforward. ∎

Lemma 2 yields the following transfer of real inequalities to their vector
companions in Euclidean spaces:

######  Theorem 7.

Suppose that $f:\mathbb{R}\rightarrow\mathbb{R}$ is a nonnegative continuous
function not identically zero and $\varphi:[0,\infty)\rightarrow\mathbb{R}$ is
a continuous function such that

$f(\gamma t)=\varphi(\gamma)f(t)$

for all $\gamma\geq 0$ and $t\in\mathbb{R}.$ If $A=(a_{ik})_{i,k}$ is a real
$m\times r$ matrix, $B=(b_{jk})_{j,k}$ is a real $n\times r$ matrix and
$(\lambda_{i})_{i=1}^{m}$ and $(\mu_{j})_{j=1}^{n}$ are two families of real
numbers such that

$\sum\nolimits_{i=1}^{m}\lambda_{i}f\left(\sum\nolimits_{k=1}^{r}a_{ik}t_{k}\right)\leq\sum\nolimits_{j=1}^{n}\mu_{j}f\left(\sum\nolimits_{k=1}^{r}b_{jk}t_{k}\right)$

for all $t_{1},...,t_{r}\in\mathbb{R},$ then

$\sum\nolimits_{i=1}^{m}\lambda_{i}\varphi\left(\left\|\sum\nolimits_{k=1}^{r}a_{ik}\mathbf{x}_{k}\right\|_{2}\right)\leq\sum\nolimits_{j=1}^{n}\mu_{j}\varphi\left(\left\|\sum\nolimits_{k=1}^{r}b_{jk}\mathbf{x}_{k}\right\|_{2}\right)$

for every family $\mathbf{x}_{1},...,\mathbf{x}_{r}$ of vectors in the
Euclidean space $\mathbb{R}^{N}$.

###### Proof.

We apply Lemma 2 to the function

$\Phi(\mathbf{y},\mathbf{x})=f\left(\langle\mathbf{y},\mathbf{x}\rangle\right),$

by noticing that in this case the value of constancy $C(\Phi)$ is strictly
positive.

Fix arbitrarily $\mathbf{u}\in S^{r-1}$ and put
$t_{k}=\langle\mathbf{x}_{k},\mathbf{u}\rangle.$ According to our hypotheses,

$\sum\nolimits_{i=1}^{m}\lambda_{i}f\left(\langle\sum\nolimits_{k=1}^{r}a_{ik}\mathbf{x}_{k},\mathbf{u}\rangle\right)\leq\sum\nolimits_{j=1}^{n}\mu_{j}f\left(\langle\sum\nolimits_{k=1}^{r}b_{jk}\mathbf{x}_{k},\mathbf{u}\rangle\right),$

whence, according to Lemma 2 we infer that

$C(\Phi)\sum\nolimits_{i=1}^{m}\lambda_{i}\varphi\left(\left\|\sum\nolimits_{k=1}^{r}a_{ik}\mathbf{x}_{k}\right\|_{2}\right)=\sum\nolimits_{i=1}^{m}\lambda_{i}\int_{S^{N-1}}f\left(\langle\sum\nolimits_{j=1}^{r}a_{ij}\mathbf{x}_{j},\mathbf{u}\rangle\right)d\mathbf{u}\\\
\leq\sum\nolimits_{j=1}^{n}\mu_{j}\int_{S^{N-1}}f\left(\langle\sum\nolimits_{k=1}^{r}b_{jk}\mathbf{x}_{k},\mathbf{u}\rangle\right)d\mathbf{u}=C(\Phi)\sum\nolimits_{j=1}^{n}\mu_{j}\varphi\left(\left\|\sum\nolimits_{k=1}^{r}b_{jk}\mathbf{x}_{k}\right\|_{2}\right).$

The proof ends by simplifying the end sides by $C(\Phi).$ ∎

In the particular case when $f(t)=\varphi(t)=\left|t\right|^{p}$ and $p>0$,
Theorem 7 reads as follows:

######  Corollary 2.

Suppose that $A=(a_{ik})_{i,k}$ is a real $m\times r$ matrix,
$B=(b_{jk})_{j,k}$ is a real $n\times r$ matrix and $(\lambda_{i})_{i=1}^{m}$
and $(\mu_{j})_{j=1}^{n}$ are two families of real numbers. If for some
$\alpha>0,$

$\sum\nolimits_{i=1}^{m}\lambda_{i}\left|\sum\nolimits_{k=1}^{r}a_{ik}t_{k}\right|^{\alpha}\leq\sum\nolimits_{j=1}^{n}\mu_{j}\left|\sum\nolimits_{k=1}^{r}b_{jk}t_{k}\right|^{\alpha}$

for all $t_{1},...,t_{r}\in\mathbb{R},$ then

$\sum\nolimits_{i=1}^{m}\lambda_{i}\left\|\sum\nolimits_{k=1}^{r}a_{ik}\mathbf{x}_{k}\right\|_{2}^{\alpha}\leq\sum\nolimits_{j=1}^{n}\mu_{j}\left\|\sum\nolimits_{k=1}^{r}b_{jk}\mathbf{x}_{k}\right\|_{2}^{\alpha}$

for every family $\mathbf{x}_{1},...,\mathbf{x}_{r}$ of vectors in the
Euclidean space $\mathbb{R}^{N}$.

######  Corollary 3.

$($Levi’s reduction theorem _[25]_$)$ Every piecewise linear inequality of the
form

$\sum_{i=1}^{n}\lambda_{i}\left|\sum_{k=1}^{r}a_{ik}t_{k}\right|\geq 0,$

which holds for all $n$-tuples $t_{1},...,t_{n}$ of real numbers remains true
when absolute value function is replaced by the Euclidean norm and
$t_{1},...,t_{r}$ are arbitrary elements of $\mathbb{R}^{N}$.

It is straightforward that both Corollaries 2 and 3 extend verbatim to the
case of finite families of vectors in an arbitrary inner product spaces.

Levi deduced the Hornich-Hlawka inequality as a consequence of Corollary 3,
but his approach also yields the following more general inequality,

(6.1) $\sum\left\|\pm x_{1}\pm x_{2}\pm\cdots\pm x_{n}\right\|_{2}\geq
2\binom{n-1}{[(n-1)/2]}\sum_{k=1}^{n}\left||x_{k}\right\|_{2},$

where the summation on the left is taken over all $2^{n}$ permutation of the
$\pm$ signs and $[t]$ is the integer part function (that is, the largest
integer less than or equal to $t$).

The Rădulescu brothers applied Levi’s reduction theorem to prove the following
generalization of Dobrushin’s inequality (see [44], Theorem 3.3): Let
$A=(a_{ij})_{i,j}$ be a real $m\times n$ dimensional matrix and $H$ a real
Hilbert space. Then

(6.2)
$\sum_{i=1}^{m}\left\|\sum_{j=1}^{n}a_{ij}x_{j}\right\|\leq\bar{\alpha}_{m,n}(A)\sum_{k=1}^{n}\left\|\mathbf{x}_{k}\right\|+(\left\|A\right\|_{1}-\bar{\alpha}_{m,n}(A))\left\|\sum_{k=1}^{n}\mathbf{x}_{k}\right\|$

for all $\mathbf{x}_{1},...,\mathbf{x}_{n}\in H.$ Here

$\bar{\alpha}_{m,n}(A)=\frac{1}{2}\max_{r,s}\sum_{i=1}^{m}\left|a_{ir}-a_{is}\right|\quad\text{and\quad}\left\|A\right\|_{1}=\max_{1\leq
j\leq n}\sum_{i=1}^{m}\left|a_{ij}\right|.$

The Hornich-Hlawka inequality can be recover from 6.2 by considering the
particular case when $H=\mathbb{R}^{3}$ and

$A=\left(\begin{array}[c]{ccc}0&1&1\\\ 1&0&1\\\ 1&1&0\end{array}\right).$

In this case $\bar{\alpha}_{m,n}(A)=1$ and $\left\|A\right\|_{1}=2.$

An unexpected generalization of the inequality (2.1) to the framework of
functions mixing suitable conditions of higher-order convexity has been
recently discovered by Ressel [45]. We state it here following [32]:

######  Theorem 8.

If $f:\mathbb{R}_{+}\rightarrow\mathbb{R}$ is a continuous function of class
$C^{3}$ on $(0,\infty)$ such that $f^{\prime}\geq 0,$ $f^{\prime\prime}\leq 0$
and $f^{\prime\prime\prime}\geq 0,$ then

$f\left(\left|x\right|\right)+f\left(\left|y\right|\right)+f\left(\left|z\right|\right)+f\left(\left|x+y+z\right|\right)\geq
f\left(\left|x+y\right|\right)+f\left(\left|y+z\right|\right)+f\left(\left|z+x\right|\right)+f(0)$

for all $x,y,z\in\mathbb{R}.$

Since all the functions $t^{\alpha}$ $($for $0<\alpha\leq 1)$ fulfill the
hypotheses of Theorem 8, it follows that

$\left|x\right|^{\alpha}+\left|y\right|^{\alpha}+\left|z\right|^{\alpha}+\left|x+y+z\right|^{\alpha}\geq\left|x+y\right|^{\alpha}+\left|y+z\right|^{\alpha}+\left|z+x\right|^{\alpha}\text{\quad}$

for all $x,y,z\in\mathbb{R}$ and $\alpha\in(0,1].$ Combining this with
Corollary 2 one obtains the following generalization of the Hornich-Hlawka
inequality:

######  Theorem 9.

In every inner product space $E=(E,\left\|\cdot\right\|_{2}),$

$\left\|\mathbf{x}\right\|_{2}^{\alpha}+\left\|\mathbf{y}\right\|_{2}^{\alpha}+\left\|\mathbf{z}\right\|_{2}^{\alpha}+\left\|\mathbf{x}+\mathbf{y}+\mathbf{z}\right\|_{2}^{\alpha}\geq\left\|\mathbf{x}+\mathbf{y}\right\|_{2}^{\alpha}+\left\|\mathbf{y}+\mathbf{z}\right\|_{2}^{\alpha}+\left\|\mathbf{z}+\mathbf{x}\right\|_{2}^{\alpha}.$

for all $\mathbf{x},\mathbf{y},\mathbf{z}\in E$ and all $\alpha\in(0,1].$

Theorem 9 improves a previous result due to P. Ressel [45], Theorem 2, who
noticed it, for the exponents $\alpha\in\\{2,1,1/2,1/2^{2},...\\}.$

Applying Theorem 8 to the function $f(x)=\ln(1+x)$ one obtains the
multiplicative analog of the inequality (2.1),

$(1+\left|x\right|)(1+\left|y\right|)(1+\left|z\right|)(1+\left|x+y+z\right|)\allowbreak\\\
\geq(1+\left|x+y\right|)(1+\left|y+z\right|)(1+\left|z+x\right|),$

for all $x,y,z\in\mathbb{R}.$ No extension of this remark to the case of inner
product spaces is known.

######  Problem 5.

The Fréchet identity shows that the Theorem 9 also works for $\alpha=2.$ For
which other values of $\alpha\in(1,2)$ does this theorem remain true?

##  7\. The generalization of a result due to Ressel

As was mentioned in the previous section, Ressel showed that the Fréchet
identity implies the truth of Theorem 9 for the exponents
$\alpha\in\\{2,1,1/2,1/2^{2},...\\}.$ A more general result was noticed by X.
Luo [31], who considered the framework of Banach spaces:

######  Theorem 10.

Suppose $E$ is a vector space and $\varphi:E\rightarrow\mathbb{R}$ is a
function which verifies the condition

(7.1)
$\left|\varphi(\mathbf{x})-\varphi(\mathbf{y})\right|\leq\varphi(\mathbf{x}+\mathbf{y})\leq\varphi(\mathbf{x})+\varphi(\mathbf{y})$

for all $\mathbf{x},\mathbf{y}\in E$. If $\varphi^{2}$ verifies the Hornich-
Hlawka functional inequality, that is, if

(7.2)
$\sum\limits_{k=1}^{3}{\varphi}^{2}{\left(\mathbf{x}_{k}\right)}+{\varphi}^{2}\left({\sum\limits_{k=1}^{3}}\mathbf{x}_{k}\right)\geq\sum\limits_{1\leq{i}<{j}\leq
3}{\varphi}^{2}{\left(\mathbf{x}{{{}_{i}+}}\mathbf{x}_{j}\right)}$

for all $\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3}\in E,$ then so does
$\varphi.$

Clearly, every function $\varphi$ which verifies the condition (7.1) is
subadditive and nonnegative. Moreover, every even and subadditive function
$\varphi:E\rightarrow\mathbb{R}$ (in particular, every seminorm) verifies the
condition (7.1).

Taking into account the Fréchet identity, it is now clear that Theorem 10
implies the original Hornich-Hlawka inequality.

If $\varphi:E\rightarrow\mathbb{R}$ is even and subadditive and
$S:\mathbb{R}_{+}\mathbb{\rightarrow R}_{+}$ is a concave function, then
$S\circ\varphi$ verifies the condition (7.1). Indeed, the function $S$ is
subadditive and increasing, which implies that $S\circ\varphi$ is an even and
subadditive function. This implies the following

######  Corollary 4.

If $E=(E,\left\|\cdot\right\|)$ is a Hornich-Hlawka space, then
$\left\|\cdot\right\|^{\alpha}$ verifies the Hornich-Hlawka inequality for all
exponents $\alpha\in\\{1,1/2,1/2^{2},...\\}.$

Our proof of Theorem 10 is based on the following auxiliary result, inspired
by a paper of D. M. Smiley and M. F. Smiley [51].

######  Lemma 3.

Let $a,b,c,d,x,y,z$ nonnegative real numbers such that the following three
conditions are fulfilled:

$(i)\ x\leq a+b,\ y\leq b+c~{}$and $z\leq c+a;$

$(ii)\ a+b+c\geq d~{}$and $a+b+c+d\geq\max\left\\{a+b+x,b+c+y,c+a+z\right\\};$

$(iii)\ a^{2}+b^{2}+c^{2}+d^{2}\geq x^{2}+y^{2}+z^{2}.$

Then $a+b+c+d\geq x+y+z.$

###### Proof.

Indeed,

$\left(a+b+c\right)^{2}-d^{2}=a^{2}+b^{2}+c^{2}+2ab+2ac+2bc-d^{2}\\\ \leq
2\left(a^{2}+b^{2}+c^{2}+ab+bc+ca\right)-x^{2}-y^{2}-z^{2}\\\
=\left(a+b+x\right)\left(a+b-x\right)+\left(b+c+y\right)\left(b+c-y\right)+\left(c+a+z\right)\left(c+a-z\right)\\\
\leq\left(2a+2b+2c-x-y-z\right)\max\left\\{a+b+x,b+c+y,c+a+z\right\\},$

whence

$\left(a+b+c+d\right)\left(a+b+c-d\right)\\\ \leq\left(2a+2b+2c-x-
y-z\right)\max\left\\{a+b+x,b+c+y,c+a+z\right\\}.$

Combining the last inequality with $\left(ii\right)$ we get

$a+b+c-d\leq 2a+2b+2c-x-y-z,$

that is,

$x+y+z\leq a+b+c+d.$

∎

###### Proof of Thorem 10.

Put

$\displaystyle a$ $\displaystyle=\varphi\left(x_{1}\right),\
b=\varphi\left(x_{2}\right),\ c=\varphi\left(x_{3}\right),\
d=\varphi\left(x_{1}+x_{2}+x_{3}\right),$ $\displaystyle x$
$\displaystyle=\varphi\left(x_{1}+x_{2}\right),\
y=\varphi\left(x_{2}+x_{3}\right),\ z=\varphi\left(x_{3}+x_{1}\right).$

Clearly $a,b,c,d,x,y,z$ are nonnegative numbers that verify condition
$\left(i\right)$ of Lemma 3 because $\varphi$ is a subadditive function.
Condition $\left(ii\right)$ follows from the fact that $\varphi$ verifies the
condition (7.1), while condition $(iii)$ represents the fact that
$\varphi^{2}$ verifies the Hornich-Hlawka inequality.

Therefore the conclusion of Theorem 10 is a direct consequence of Lemma 3. ∎

##  8\. The case of arbitrary large families of elements

The aforementioned paper of D. M. Smiley and M. F. Smiley [51] led P. M. Vasić
and D. D. Adamović [56] to an inductive scheme generating inequalities. We
state here a slightly modified version of their result as appeared in [34],
Theorem 2, p. 528:

######  Theorem 11.

Suppose that $\varphi$ is real-valued function defined on a commutative
additive semigroup $\mathcal{S}$ such that

$\sum\limits_{1\leq{i}<{j}\leq
3}{\varphi\left({{x{{}_{i}+x}}}_{j}\right)}\leq\sum\limits_{k=1}^{3}{\varphi\left(x_{k}\right)}+{\varphi}\left({\sum\limits_{k=1}^{3}}x_{k}\right)$

for all $x_{1},x_{2},x_{3}\in\mathcal{S}.$ Then for each pair
$\left\\{k,n\right\\}$ of integers with $2\leq k<n$ we also have

$\sum\limits_{1\leq{i_{1}}<...<{i_{k}}\leq
n}{\varphi\left({\sum\limits_{j=1}^{k}{x{{}_{i_{j}}}}}\right)}\leq\binom{n-2}{k-1}\sum\limits_{k=1}^{n}{\varphi\left(x_{k}\right)}+\binom{n-2}{k-2}{\varphi}\left({\sum\limits_{k=1}^{n}}x_{k}\right)$

whenever $x_{1},...,x_{n}\in\mathcal{S}.$

######  Corollary 5.

Under the hypotheses of Theorem _11_ ,

$\sum\limits_{k=2}^{n-1}\sum\limits_{1\leq{i_{1}}<...<{i_{k}}\leq
n}{\varphi\left({\sum\limits_{j=1}^{k}{x{{}_{i_{j}}}}}\right)}\leq\left(2^{n-2}-1\right)\left(\sum\limits_{k=1}^{n}{\varphi\left(x_{k}\right)}+{\varphi}\left({\sum\limits_{k=1}^{n}}x_{k}\right)\right).$

By combining Theorem 9 and Theorem 11 we infer the following _fractional_
_power inequalities_ valid in the context of real inner product spaces:

$\sum_{1\leq i_{1}<\cdots<i_{k}\leq
n}\left\|\mathbf{x}_{i_{1}}+\cdots+\mathbf{x}_{i_{k}}\right\|^{\alpha}\leq\binom{n-2}{k-2}\left(\frac{n-k}{k-1}\sum_{k=1}^{n}\left\|\mathbf{x}_{k}\right\|^{\alpha}+\left\|\sum_{k=1}^{n}\mathbf{x}_{k}\right\|^{\alpha}\right)$

where $1\leq k\leq n-1,$ $n=3,4,5,...$ and $\alpha\in(0,1]$ $).$ This includes
(for $\alpha=1)$ the family of inequalities proved independently by D. Z.
Djoković [8] and D. M. Smiley and M. F. Smiley [51].

##  9\. Hornich-Hlawka operators?

It is a common practice in mathematics to study the operator analogs of some
Banach space properties. The study of the Hornich Hlawka inequality leads
naturally to the following class of continuous and linear operators acting on
Banach spaces. A continuous linear operator $T:X\rightarrow Y$ is called a
_Hornich-Hlawka operator_ if there exists a constant $C>0$ such that

$\left\|Tx+Ty\right\|+\left\|Ty+Tz\right\|+\left\|Tz+Tx\right\|\leq\left\|T\right\|\left(\left\|\mathbf{x}\right\|+\left\|\mathbf{y}\right\|+\left\|\mathbf{z}\right\|+\left\|\mathbf{x}+\mathbf{y}+\mathbf{z}\right\|\right)$

for all $x,y,z\in X.$

According to Theorem 11, the Hornich-Hlawka operators also verify inequalities
of the form

$\sum_{1\leq i_{1}<\cdots<i_{k}\leq
n}\left\|Tx_{i_{1}}+\cdots+Tx_{i_{k}}\right\|\leq\binom{n-2}{k-2}\left\|T\right\|\left(\frac{n-k}{k-1}\sum_{k=1}^{n}\left\|x_{k}\right\|+\left\|\sum_{k=1}^{n}x_{k}\right\|\right)$

whenever $1\leq k\leq n-1$ and $n=3,4,5,...~{}.$

A Banach space $E$ is a Hornich-Hlawka space if the identity of $E$ is a
Hornich-Hlawka operator.

It is straightforward that every bounded linear operator that factors through
a Hornich-Hlawka space is a Hornich-Hlawka operator and the class of Hornich-
Hlawka operators forms an ideal of operators in the sense of Pietsch [40].

It is too early to appreciate the usefulness of the Hornich-Hlavka type
operators, but the following problem deserves to be under attention:

######  Problem 6.

Does every Hornich-Hlawka operator admit a factorization through a Hornich-
Hlawka space?

##  10\. Further Comments

We gain more insight into the Hornich-Hlawka inequality by appealing to the
harmonic analysis. The necessary information can be found in the book of C.
Berg, J. P. R. Christensen and P. Ressel [2], Chapter 4, Section 6.

For this, suppose that $C$ is a real linear space or a convex cone of it ($C$
may be open). A continuous function $f:C\rightarrow\mathbb{R}$ verifies the
_Hornich-Hlawka functional equation_ if

$f\left(\mathbf{x}\right)+f\left(\mathbf{y}\right)+f\left(\mathbf{z}\right)+f\left(\mathbf{x}+\mathbf{y}+\mathbf{z}\right)\geq
f\left(\mathbf{x}+\mathbf{y}\right)+f\left(\mathbf{y}+\mathbf{z}\right)+f\left(\mathbf{z}+\mathbf{x}\right)+f(0)$

for all $\mathbf{x},\mathbf{y},\mathbf{z}\in C;$ The last term $f(0)$ can be
eliminated by replacing $f$ by $f-f(0)$ (or simply by deleting it if $f(0)\geq
0).$

Among the people who contributed to the study of this functional equation we
mention here T. Popoviciu [42], H. S. Witsenhausen [60] and W. Fechner [10].

When $C=(0,\infty)$, then both the completely monotone functions and the
Bernstein functions verifies _Hornich-Hlawka functional equation_. See H. S.
Sendov and R. Zitikis [48], Corollary 4.3.

The significance of this functional equation is made clear by its connection
with iterated differences.

The _difference operator_ $\Delta_{\mathbf{h}}$ $($of step size $\mathbf{h}\in
C)$ associates to each function $f:E\rightarrow\mathbb{R}$ the function
$\Delta_{\mathbf{h}}f$ defined by the formula

$\left(\Delta_{\mathbf{h}}\mathbf{f}\right)(\mathbf{x})=f(\mathbf{x}+\mathbf{h})-f(\mathbf{x}),\quad\text{for
all }\mathbf{x},\mathbf{h}\in C.$

The difference operators are linear and commute to each other,

$\Delta_{\mathbf{h}_{1}}\Delta_{\mathbf{h}_{2}}=\Delta_{\mathbf{h}_{2}}\Delta_{\mathbf{h}_{1}},\quad\text{for
all }\mathbf{h}_{1},\mathbf{h}_{2}\in C.$

A continuous function $f:C\rightarrow\mathbb{R}$ is called n-_monotone_ if
$f\geq 0$ and

$(-1)^{n}\Delta_{\mathbf{x}_{1}}\Delta_{\mathbf{x}_{2}}\cdots\Delta_{\mathbf{x}_{n}}f(\mathbf{x})\geq
0$

for all $\mathbf{x},\mathbf{x}_{1},...,\mathbf{x}_{n}\in C;$ the function
$f:C\rightarrow\mathbb{R}$ is called $n$-_alternating_ if it is continuous and

$(-1)^{n}\Delta_{\mathbf{x}_{1}}\Delta_{\mathbf{x}_{2}}\cdots\Delta_{\mathbf{x}_{n}}f(\mathbf{x})\leq
0$

for all $\mathbf{x},\mathbf{x}_{1},...,\mathbf{x}_{n}\in C.$ If $f$ is
$3$-alternating, then

$\Delta_{\mathbf{x}}\Delta_{\mathbf{y}}\Delta_{\mathbf{z}}f(\mathbf{v})=f\left(\mathbf{x}+\mathbf{v}\right)+f\left(\mathbf{y}+\mathbf{v}\right)+f\left(\mathbf{z}+\mathbf{v}\right)+f\left(\mathbf{x}+\mathbf{y}+\mathbf{z}+\mathbf{v}\right)\\\
-f\left(\mathbf{x}+\mathbf{y}+\mathbf{v}\right)-f\left(\mathbf{y}+\mathbf{z}+\mathbf{v}\right)-f\left(\mathbf{z}+\mathbf{x}+\mathbf{v}\right)-f(\mathbf{v})\geq
0,$

for all $\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{v}\in C,$ which implies that
$f$ is a solution of the Hornich-Hlawka functional equation. In this way, the
study of this functional equation can be reduced to the study of
$3$-alternating function.

The paper of C. P. Niculescu and S. Sra [38] includes several example of
functions of several variables that verify the Hornich-Hlawka functional
equation. In particular it is shown that the restriction of the function
$\det$ to the cone Sym${}^{+}(n,\mathbb{R})$ of all $n\times n$-dimensional
positive semidefinite matrices has positive differences of any order. This
implies the determinantal Hornich-Hlawka inequality of M. Lin [27],

$\det A+\det B+\det
C+\det(A+B+C)\geq\det\left(A+B\right)+\det\left(B+C\right)+\det\left(C+A\right),$

for all $A,B,C\in\;$Sym${}^{+}(n,\mathbb{R}).$

As is well known, the complete metric spaces with a global nonpositive
curvature display many nice properties that make them a natural generalization
of Hilbert spaces. See M. Bačák [1] and the references therein. Except for a
paper by D. Serre [49], nothing is known about the Hornich-Hlawka inequalities
in this context. No doubt, this qualifies as a subject that deserves to be
investigated.

Acknowledgement. The authors would like to thank Ştefan Cobzaş from University
Babeş-Bolyai, Cluj-Napoca, for many useful comments on the subject of this
paper.

## References

  * [1] Bačák, M.: Convex Analysis and Optimization in Hadamard Spaces. Series in Nonlinear Analysis and Applications, vol. 22, Walter de Gruyter & Co., Berlin (2014)
  * [2] Berg, C., Christensen, J.P.R., Ressel P.: Harmonic Analysis on Semigroups. Graduate Texts in Mathematics, vol. 100. Springer-Verlag, Berlin (1984)
  * [3] Bretagnolle, J., Dacunha-Castelle, D., Krivine, J.L.: _Lois stables et espaces_ $L_{p}$. Ann. Inst. H. Poincaré Probab. Statist. 2, 231–259 (1966)
  * [4] Clarkson, J.A.: The von Neumann-Jordan constant for the Lebesgue space, Ann. of Math. 38, 114–115 (1937)
  * [5] D. Dacunha-Castelle and J. L. Krivine, _Applications des ultraproduits à l’étude des espaces et des algèbres de Banach_ , Studia Math. 41 (1972), 315–344.
  * [6] L. Diening, P. Harjulehto, P. Hästö and M. Ruzicka, _Lebesgue and Sobolev Spaces with Variable Exponents_ , Springer (2011).
  * [7] J. Diestel and J. Jr. Uhl, _Vector Measures_ , Mathematical Surveys, vol. 15, Providence, R.I., American Mathematical Society, 1977.
  * [8] D. Z. Djokovic, _Generalizations of Hlawka’s inequality_ , Glas. Mat. Fiz. Astronom. Ser. II Drustvo Mat. Fiz. Hrvatske 18 (1963), 169-175.
  * [9] L. E. Dor, _Potentials and isometric embeddings in_ $L^{1},$ Israel Journal of Mathematics 24 (1976), no. 3, 260–268.
  * [10] W. Fechner, _Hlawka’s functional inequality_ , Aequat. Math. 87 (2014), 71–87.
  * [11] Th. S. Ferguson, _A representation of the symmetric bivariate Cauchy distribution_ , Ann. Math. Statist. 33 (1962), 1256–1266.
  * [12] T. Figiel, _A short proof of Dvoretzky’s theorem on almost spherical sections of convex bodies_ , Compositio Mathematica 33 (1976), 297–301.
  * [13] L. Giugiuc, _Proposed Problem_ 11841, Amer. Math. Monthly 122 (2015), no. 5, 500.
  * [14] M. Fréchet, _Sur la definition axiomatique d’une classe d’espaces vectoriels distanciés applicables vectoriellement sur l’espace de Hilbert_ , Ann. of Math. 36 (1935), 705–718.
  * [15] C. Herz, _A class of negative-definite functions_ , Proc. Amer. Math. Soc. 14 (1963), 670–676.
  * [16] C. Herz, _The theory of_ $p$-_spaces with an application to convolution operators_ , Trans. Amer. Math. Soc. 154 (1971) 69–82.
  * [17] H. Hornich, Eine Ungleichung für Vektorlängen, Math. Z. 48 (1942), 268–274.
  * [18] R. C. James, Uniformly non-square Banach spaces, Ann. of Math. 80 (1964), 542–550.
  * [19] P. Jordan and J. von Neumann, _On inner products in linear metric spaces_ , Ann. of Math. 36 (1935), 719–723.
  * [20] M. I. Kadets, _Linear dimension of the spaces_ $L_{p}$ _and_ $\ell_{q}$ (Russian), Uspekhi Mat. Nauk 13 (1958), 95–98.
  * [21] M. Kato, L. Maligranda and Y. Takahashi, _On James and Jordan-von Neumann_ _constants and the normal structure coefficient of Banach spaces_ , Studia Mathematica 144(3) (2001), 275–295.
  * [22] M. Kato and Y. Takahashi, _On the von Neumann-Jordan constant for Banach spaces_ , Proc. Amer. Math. Soc. 125 (4) (1997), 1055–1062.
  * [23] A. Koldobsky, _Generalized Lévy representation of norms and isometric embeddings into_ $L_{p}$– _spaces_ , Ann. Inst. Poincaré 28 (1992), 335–353.
  * [24] A. Koldobsky, _Positive definite distributions and subspaces of_ $L_{p}$ _with applications to stable processes_ , Canad. Math. Bull. 42 (1999) 344–353.
  * [25] F. W. Levi, _Ein Reduktionsverfahren für lineare Vektorungleichungen_ , Archiv der Mathematik 2 (1949), 24–26.
  * [26] P. Levy, _Théorie de l’addition des variables aléatoires_ , Gauthier-Villars, Paris, 1937.
  * [27] M. Lin, _A determinantal inequality for positive semidefinite matrices_ , The Electronic Journal of Linear Algebra 27 (2014), 821–826.
  * [28] J. Lindenstrauss, _On the extension of operators with a finite-dimensional range_ , Illinois J. Math. 8 (1964), 488–499
  * [29] J. Lindenstrauss and A. Pełczyński, _Absolutely summing operators in_ $\mathcal{L}_{p}$– _spaces and their applications_ , Studia Math. 29 (1968), 275–326.
  * [30] J. Lindenstrauss and H. P. Rosenthal, _The_ $\mathcal{L}_{p}$ _spaces_ , Israel Journal of Mathematics 7 (1969), 325–349.
  * [31] X. Luo, _Interactions between Hlawka Type_ -1 _and Type_ -2 _Quantities_ , Math. Inequal. Appl. 24 (2021), Number 4, 913–925.
  * [32] D. S. Marinescu and C. P. Niculescu, _Old and new on the_ $3$_-convex functions_ , Math. Inequal. Appl. 26 (2023), No. 4, 911–933.
  * [33] D. S. Mitrinović, _Analytic Inequalities_ (in cooperation with P. M. Vasić), Die Grundlehren der mathematischen Wissenschaften, 165, Springer-Verlag, 1970.
  * [34] D. S. Mitrinović, J. E. Pečarić and A. M. Fink, _Classical and New inequalities in Analysis_ , Kluwer Academic Publishers, Dordrecht, 1993.
  * [35] A. Neyman, _Representation of_ $L_{p}$– _norms and isometric embedding in_ $L_{p}$– _spaces_ , Israel J. Math. 48 (1984), 129–138.
  * [36] C. P. Niculescu, _Functional inequalities in the framework of Banach spaces_, arXiv preprint, May 30, 2024.
  * [37] C. P. Niculescu and L.-E. Persson, _Convex Functions and Their Applications_. _A Contemporary Approach_ , 2nd Ed., CMS Books in Mathematics vol. 23, Springer-Verlag, New York, 2018.
  * [38] C. P. Niculescu and S. Sra, _Functions with positive differences on convex cones_ , Results Math. 78 (2023), no. 6, article 217, 26 pp.
  * [39] J. Pečarić, _Modified version of a general result of Vasić-Adamović-Kečkić and some remarks concerning inequalities for convex functions_ , Glasnik Matematicki 21 (1986), no. 41, 331-341.
  * [40] A. Pietsch, _Operators Ideals_ , North-Holland, Amsterdam, 1980.
  * [41] G. Pólya, _How to Solve It. A New Aspect of Mathematical Method_ , 2nd Ed., Princeton University Press, Princeton, 1957.
  * [42] T. Popoviciu, _On some inequalities_ , Gaz. Mat., Bucureşti 51 (1946), 81–85. (Romanian)
  * [43] T. Popoviciu, _Sur certaines inégalités qui caractérisent les fonctions convexes_ , Analele ştiinţifice Univ. ”Al. I. Cuza” Iasi, Secţia I-a Mat. 11 (1965), 155–164.
  * [44] M. Rădulescu and S. Rădulescu, _Generalizations of Dobrushin’s inequalities and applications_ , J. Math. Anal. Appl. 204 (1996), 631–645.
  * [45] P. Ressel, _The Hornich–Hlawka inequality and Bernstein functions_ , J. Math. Inequal. 9 (2015), 883-888.
  * [46] R. Schilling, R. Song and Z. Vondraček, _Bernstein Functions_ , Theory and Applications 2nd ed., De Gruyter, Berlin, 2010.
  * [47] I.J. Schoenberg, _Metric spaces and positive definite functions_ , Trans. Amer. Math. Soc. 44 (1938), 522–536.
  * [48] H. S. Sendov and R. Zitikis, _The shape of the Borwein–Affleck–Girgensohn function generated by completely monotone and Bernstein functions_ , J. Optim. Theory Appl. 160 (2014), 67–89.
  * [49] D. Serre, _The reverse Hlawka inequality in a Minkowski space_ , C. R. Acad. Sci. Paris, Ser. I 353 (2015), 629–63.
  * [50] A. Simon and P. Volkmann, _On two geometric inequalities_ , Ann. Math. Sil. 9 (1995), 137–140.
  * [51] D. M. Smiley and M. F. Smiley, _The polygonal inequalities_ , Amer. Math. Monthly 71 (1964), 755–760.
  * [52] S.-E. Takahashi, Y. Takahashi and S. Wada, _An extension of Hlawka’s inequality_ , Math. Inequal. Appl. 3 (2000), 63–67.
  * [53] Y. Takahashi, S. E. Takahasi, S. Wada, _Some convexity constants related to Hlawka type inequalities in Banach spaces_ , J. of Inequal. Appl. 7 (2002), no. 1, 125–141.
  * [54] S.-E. Takahashi, Y. Takahashi and S. Wada, _A general Hlawka inequality and its reverse inequality_ , Math. Inequal. Appl. 12 (2009), 1–10.
  * [55] R. F. Tichy, Nachruf auf Edmund Hlawka, Monatsh Math 158 (2009), 107–120.
  * [56] P. M. Vasić and D. D. Adamović, _Sur un système infini d’inégalités fonctionnelles_ , Publ. Inst. Math. Nouv. Sér. 9 (23), 107–114 (1969)
  * [57] S. Wada, _Inequalities of Hlawka type for matrices_ , Archiv der Mathematik 77 (2001), 415–422.
  * [58] M. Willem, _Functional Analysis_ : _Fundamentals and Applications_ , Springer Science & Business Media, 2013.
  * [59] L. R. Williams and J. H. Weels, $L^{p}$ _inequalities_ , J. Math. Anal. Appl. 64 (1978), 518-529.
  * [60] H. S. Witsenhausen, _Metric inequalities and the zonoid problem_ , Proc. Amer. Math. Soc. 40 (1973) No. 2, 517–520.
  * [61] *** A short CV of Hans Hornich


# ON GENERALIZED LIST $\operatorname{\mathcal{G}}$-FREE COLOURINGS OF GRAPHS

Yaser Rowshan1 1Y. Rowshan, Department of Mathematics, Institute for Advanced
Studies in Basic Sciences (IASBS), Zanjan 45137-66731, Iran.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

For given graph $H$ and graphical property $P$, the conditional chromatic
number $\chi(H,P)$ of $H$, is the smallest number $k$, so that $V(H)$ can be
decomposed into sets $V_{1},V_{2},\ldots,V_{k}$, in which $H[V_{i}]$ satisfies
the property $P$, for each $1\leq i\leq k$. When property $P$ be that each
color class contains no copy of $G$, we write $\chi_{G}(H)$ instead of
$\chi(G,P)$, which is called the $G$-free chromatic number. Due to this, we
say $H$ has a $k$-$G$-free coloring if there is a map
$c:V(H)\longrightarrow\\{1,\ldots,k\\}$, so that each of the color classes of
$c$ be $G$-free. Assume that for each vertex $v$ of a graph $H$ is assigned a
set $L(V)$ of colors, called a color list. Set $g(L)=\\{g(v):v\in V(H)\\}$,
that is the set of colors chosen for the vertices of $H$ under $g$. An
$L$-coloring $g$ is called $G$-free, so that:

  * •

$g(v)\in L(v)$, for any $v\in V(H)$.

  * •

$H[V_{i}]$ is $G$-free for each $i=1,2,\ldots,L$.

If there exists an $L$-coloring of $H$, then $H$ is called $L$-$G$-free-
colorable. A graph $H$ is said to be $k$-$G$-free-choosable if there exists an
$L$-coloring for any list-assignment $L$ satisfying $|L(V)|\geq k$ for each
$v\in V(H)$, and $H[V_{i}]$ be $G$-free for each $i=1,2,\ldots,L$. Let graph
$H$ and a collection of graphs $\operatorname{\mathcal{G}}$ are given, the
$\chi_{\operatorname{\mathcal{G}}}^{L}(H)$ of $H$ is the last integer $k$, so
that $H$ is $k$-$\operatorname{\mathcal{G}}$-free-choosable i.e. $H[V_{i}]$ is
$\operatorname{\mathcal{G}}$-free for each $i=1,2,\ldots,k$ i.e. contains no
copy of any member of $\operatorname{\mathcal{G}}$. In this article, we
determin some upper bounds for $\chi_{G}^{L}(H)$, in term of the
$\Delta(H),|V(H)|$ and $\delta(G)$. In particular, we show that
$\chi_{G}^{L}(H)=\chi_{G}(H)$ for some graph $H$ and $G$,
$\chi_{G}^{L}(H\oplus H^{\prime})\leq\chi_{G}^{L}(H)+\chi_{G}^{L}(H^{\prime})$
for each $G$, $H$, and $H^{\prime}$. Also, we show that
$\chi_{\operatorname{\mathcal{G}}}(H\oplus
K_{n})=\chi^{L}_{\operatorname{\mathcal{G}}}(H\oplus K_{n})$, where
$\operatorname{\mathcal{G}}$ is a collection of all $d$-regular graphs, and
some $n$.

###### Key words and phrases:

$\operatorname{\mathcal{G}}$-free Subset, $k$-choosable, $d$-regular graphs,
Conditional Coloring, Vertex Arboricity, $L$-$G$-free-colorable.

###### 2010 Mathematics Subject Classification:

05C15.

##  1\. Introduction

All graphs $G$ considered here are undirected, simple, and finite graphs. For
given graph $H=(V(H),E(H))$, the maximum degree of $H$ is denoted by
$\Delta(H)$, and the minimum degree of $H$ is denoted by $\delta(H)$. If $v$
be a vertex of $H$, the degree and neighbors of $v$ are denoted by
$\deg_{H}{(v)}$ ($\deg{(v)}$) and $N_{H}(v)$, respectively. The join of two
graphs $G$ and $H$ is denoted by $G\oplus H$ and obtained from $G$ and $H$ by
joining each vertex of $G$ to all vertices of $H$. We use $\chi(H)$ to denote
the chromatic number of $H$. For given graph $H$, let each vertex $v$ of $H$
be assigned a set $L(V)$ of colors, called a color list. An $L$-coloring of
$H$ is a vertex-coloring $c$ so that:

  * •

For any $v\in V(H)$, $c(v)\in L(v)$.

  * •

$c(v)\neq c(v^{\prime})$ for each $vv^{\prime}\in E(H)$.

If there exists an $L$-coloring of $H$, then $H$ is called $L$-colorable. A
graph $H$ is said to be $k$-choosable if there exists $L$-coloring for any
list-assignment $L$ satisfying $|L(V)|\geq k$ for each $v\in V(H)$. The choice
number $\chi_{L}(H)$ of $H$ is the minimum integer $k$ so that $H$ is
$k$-choosable. Note that $\chi(H)\leq\chi_{L}(H)$ for any graph $H$, however,
equality does not necessarily hold. The following particular case has been
proved by Ohba [9]:

######  Theorem A.

[9] If $|V(H)|\leq\chi(H)+\sqrt{2\chi(H)}$, then:

$\chi_{L}(H)=\chi(H).$

######  Theorem B.

[9] If $|V(H)|+|V(G)|\leq\chi(H)+\chi(G)+\sqrt{2(\chi(H)+\chi(G))}$, then:

$\chi_{L}(H\oplus G)=\chi(H)+\chi(G).$

One can refer to [5, 4, 11, 7] and [14] and their references for further
studies about $L$-coloring of graph.

###  1.1. Conditional Coloring

For given graph $H$ and graphical property $P$, the conditional chromatic
number $\chi(H,P)$ of $H$, is the smallest number $k$, so that $V(H)$ can be
decomposed into sets $V_{1},V_{2}\ldots,V_{k}$, in which $H[V_{i}]$ satisfies
the property $P$, for each $1\leq i\leq k$. This extension of graph coloring
was stated by Harary in 1985 [2]. A particular state, when $P$ is the property
of being acyclic, $\chi(H,P)$ is said the vertex arboricity of $H$. The vertex
arboricity of $H$ is shown $\alpha(H)$ and is defined as the last number of
subsets in a partition of the vertex set of $H$, so that any subset induces an
acyclic subgraph. When $P$ is the property that each color class contains no
copy of $G$, we write $\chi_{G}(H)$ instead of $\chi(G,P)$, which is called
the $G$-free chromatic number. Due to this, we say a graph $H$ has a
$k$-$G$-free coloring if there exists a map
$g:V(H)\longrightarrow\\{1,\ldots,k\\}$, so that each of the color classes of
$g$ be $G$-free.

We use $\alpha_{L}(H)$ to denote the list vertex arboricity of $H$, which is
the least integer $k$, such that there exists an acyclic $L$-coloring for each
list assignment $L$ of $H$, in which $k\leq|L(v)|$. So,
$\alpha(H)\leq\alpha_{L}(H)$ for any graph $H$. It has been proved that for
each graph $H$, $\alpha(H)\leq\lceil\frac{\Delta(H)+1}{2}\rceil$ [1], and
$\alpha_{L}(H)\leq\lceil\frac{\Delta(H)+1}{2}\rceil$ [12]. When $H$ is not a
complete graph or a cycle of odd order, then
$\alpha(H)\leq\lceil\frac{\Delta}{2}\rceil$[6]. Also, it has been shown that
$\alpha(H)\leq 3,\alpha_{L}(H)\leq 3$ if $H$ be a planar graph, [1, 3, 12]. As
a generalized result of Theorem A and B, Lingyan Zhe, and Baoyindureng Wu have
proven the following theorem [13].

######  Theorem C.

[13] If $|V(H)|\leq 2\alpha(H)+\sqrt{2\alpha(H)}-1$, then:

$\alpha_{L}(H)=\alpha(H).$

Assume that each vertex $v\in V(H)$ is assigned a set $L(V)$ of colors, told a
color list. Set $c(L)=\\{c(v):v\in V(H)\\}$. An $L$-coloring $c$ is called
$G$-free, so that:

  * •

$c(v)\in L(v)$ for each $v\in V(H)$.

  * •

$H[V_{i}]$ is $G$-free for each $i=1,2,\ldots,L$.

If there exists an $L$-coloring of $H$, then $H$ is said to be $L$-$G$-free-
colorable. A graph $H$ is said $k$-$G$-free-choosable if there exists an
$L$-coloring for any list-assignment $L$ satisfying $|L(V)|\geq k$ for each
$v\in V(H)$, and $H[V_{i}]$ be $G$-free for each $i=1,2,\ldots,L$. For given
two graphs $H$ and $G$, the $\chi_{G}^{L}(H)$ of $H$ is the minimum integer
$k$, if $H$ be $k$-$G$-free-choosable.

In this article, we shall use Ohba’s idea to show similar results in terms of
$G$-free coloring, and list $G$-free coloring of graphs. In particular, in
this article, we prove the subsequent results.

######  Theorem 1.

Suppose that $H$, $H^{\prime}$, and $G$ are three graphs, where
$\delta(G)=\delta$, $H$ is a $k$-$G$-free choosable, and $H^{\prime}$ is a
$k^{\prime}$-$G$-free choosable. Suppose that $S$ and $S^{\prime}$ be the
maximum subsets of $V(H)$ and $V(H^{\prime})$, respectively, so that $H[S]$ is
$G$-free and $H^{\prime}[S^{\prime}]$ is $G$-free. In this case, if either
$(|S^{\prime}|-1)(|V(H)|+|S^{\prime}|)\leq|S^{\prime}|\delta(k+1)$ or
$(|S|-1)(|V(H^{\prime})|+|S|)\leq|S|\delta(k^{\prime}+1)$, then $H\oplus
H^{\prime}$ is a $(k+k^{\prime})$-$G$-free-choosable, that is:

$\chi_{G}^{L}(H\oplus
H^{\prime})\leq\chi_{G}^{L}(H)+\chi_{G}^{L}(H^{\prime})=k+k^{\prime}.$

######  Theorem 2.

If $|V(H)|\leq\delta\chi_{G}(H)+\sqrt{\delta\chi_{G}(H)}-(\delta-1)$, then:

$\chi_{G}^{L}(H)=\chi_{G}(H).$

######  Theorem 3.

For each two connected graphs $H$ and $G$, we have:

$\chi^{L}_{{}_{G}}(H)\leq\lceil\frac{\Delta(H)}{\delta(G)}\rceil+1.$

######  Theorem 4.

Assume that $\operatorname{\mathbb{R}}$ be a collection of all $d$-regular
graphs. For each arbitrary graph $H$, there exists a non-negative integer
$n^{\prime}$, so that $\chi_{\operatorname{\mathbb{R}}}(H\oplus
K_{n})=\chi^{L}_{\operatorname{\mathbb{R}}}(H\oplus K_{n})$, where $n$ is
integer so that for which $n^{\prime}\leq n$.

##  2\. Proof of the Main results

Before proving the main theorems, we need some basic results. Suppose that $H$
and $G$ are two graphs, and let $L$ be a list-assignment color to $V(H)$.
Assume that $S={v_{1},v_{2},\ldots,v_{m}}\subseteq V(H)$. Set
$L(S)=\cup_{i=1}^{i=m}L(v_{i})$. Now, we have the following lemma.

######  Lemma 5.

Suppose that $H$ and $G$ be two graphs, where $\delta(G)=\delta$. Let $H$ is
not $L$-$G$-free colorable. Hence there is a subset of $V(H)$ say $S$, such
that:

$|S|>\delta|L(S)|.$

###### Proof.

By contradiction, suppose that $|S|\leq\delta|L(S)|$ for each subset $S$ of
$V(H)$. Now, define the bipartite graph $B$ with bipartition $(Y,Y^{\prime})$,
where $Y=V(H)$, and $Y^{\prime}$ is the $\delta$ copies of $L(V(H))$. Also,
for any member of $Y$ say $y$, and each member of $Y^{\prime}$ say
$y^{\prime}$, $yy^{\prime}\in E(B)$ if $y^{\prime}\in L(y)$. It is clear to
say that $N_{B}(W)=\delta|L(W)|$, for each $W\subseteq V(H)$. Now, let
$S\subseteq V(H)$. By the assumption, $N_{B}(S)=\delta|L(S)|\geq|S|$,
therefore, by Hall’s theorem, there exists a matching $M$ that saturates
$V(H)$. Consider $y$ and color $y$ with the color matched by it in $M$. As
$Y^{\prime}$ is a $\delta$ copy of $L(V(H))$. Any member $y^{\prime}$ of
$L(V(H))$ appears in at most $\delta$ times as an end vertex of some edges of
the $M$. Which means that, any color of $L(H)$ is assigned in at most $\delta$
vertices of $V(H)$. Hence, we achieve a $L$-$G$-free coloring of $V(H)$, which
is impossible. Therefore the proof is complete. ∎

To prove the following lemma, we use Ohba’s notion.

######  Lemma 6.

Suppose that $H$, $H^{\prime}$, and $G$ are three graphs, where
$\delta(G)=\delta$, $|V(H^{\prime})|=n$, and $H^{\prime}$ is $G$-free, i.e
$G\nsubseteq H^{\prime}$. If $H$ be $k$-$G$-free choosable, and
$(n-1)(|V(H)|+n)\leq n\delta(k+1)$, then $H\oplus H^{\prime}$ is
$(k+1)$-$G$-free choosable, that is:

$\chi_{G}^{L}(H\oplus H^{\prime})\leq\chi_{G}^{L}(H)+1=k+1.$

###### Proof.

The proof proceeds by induction on $|V(H^{\prime})|$. Suppose that $L$ is a
$(k+1)$-list assignment of $H\oplus H^{\prime}$. For the induction basis,
first assume that $n=1$, and $V(H^{\prime})=\\{v^{\prime}\\}$. We color
$v^{\prime}$ by one of the members of $L(v^{\prime})$, say $c^{\prime}$. For
each member of $V(H)$ say $v$, assume that
$L(v)\setminus\\{c^{\prime}\\}=L^{\prime}(v)$. As for any member of $V(H)$ say
$v$, $|L^{\prime}(v)|\geq|L(v)|-1=k$, and $H$ is $k$-$G$-free choosable. Thus
$H\oplus H^{\prime}$ is $(k+1)$-$G$-free choosable. So, assume that $n\geq 2$.
Suppose that
$V^{\prime}=V(H^{\prime})=\\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{n}\\}$.
Now, by considering $\bigcap\limits_{v^{\prime}\in V^{\prime}}L(v^{\prime})$,
we have two cases as follow:

Case 1: $\bigcap\limits_{v^{\prime}\in V^{\prime}}L(v^{\prime})\neq\emptyset$.

Set $c^{\prime}\in\bigcap\limits_{v^{\prime}\in V^{\prime}}L(v^{\prime})$ and
assign $c^{\prime}$ to each member of $V(H^{\prime})$. Therefore, as
$G\nsubseteq H^{\prime}$, one can check that $H\oplus
H^{\prime}[V_{c^{\prime}}]$ is $G$-free. Now, for each member of $V(H)$ say
$v$, assume that $L(v)\setminus\\{c^{\prime}\\}=L^{\prime}(v)$. As for each
member of $V(H)$ say $v$, $|L^{\prime}(v)|\geq|L(v)|-1=k$, and $H$ is
$k$-$G$-free choosable, so $H\oplus H^{\prime}$ is a $(k+1)$-$G$-free
choosable.

Case 2: $\bigcap\limits_{v^{\prime}\in V^{\prime}}L(v^{\prime})=\emptyset$.

By contradiction, assume that $H\oplus H^{\prime}$ has no $L$-$G$-free
coloring. By Lemma 5, there must exist $S\subseteq V(H\oplus H^{\prime})$ with
$|S|>\delta|L(S)|$. Suppose that $S$ be the maximal subset of $V(H\oplus
H^{\prime})$ so that $|S|>\delta|L(S)|$.

Suppose that $V^{\prime}\subseteq S$. As $\bigcap\limits_{v^{\prime}\in
V^{\prime}}L(v^{\prime})=\emptyset$, any color in $L(V^{\prime})$ appears in
the lists of at most $n-1$ vertices of $V^{\prime}$, therefore one can say
that:

(1) $|L(S)|\geq|L(V^{\prime})|\geq\frac{n}{n-1}(k+1).$

On the other hand, by the assumption, as $(n-1)(|V(H)|+n)\leq n\delta(k+1)$,
it can be check that:

(2) $|S|\leq|V(H\oplus H^{\prime})|\leq\delta\frac{n}{n-1}(k+1).$

Therefore, by Equations 1, 2, we have $|S|\leq\delta|L(S)|$, a contradiction.
So, we may suppose that $V^{\prime}\nsubseteq S$, that is
$|V^{\prime}\setminus S|\neq 0$.

Set $V^{\prime\prime}=V(H\oplus H^{\prime})\setminus S$. Assume that
$L(v^{\prime\prime})\setminus L(S)=L^{\prime}(v^{\prime\prime})$ for each
$v^{\prime\prime}\in V^{\prime\prime}$. By considering $H[S]$ and
$H[V^{\prime\prime}]$, we have two claims as follow:

######  Claim 7.

$H[S]$ has a $L$-$G$-free coloring.

###### Proof of the Claim7.

As $(n-1)(|V(H)|+n)\leq n\delta(k+1)$, so
$(n-2)(|V(H)|+n-1)\leq(n-1)\delta(k+1)$, because this operation is an
increasing operation. Therefore, by the induction hypothesis, $H\oplus
H^{\prime}\setminus\\{v^{\prime}\\}$ is $(k+1)$-$G$-free list colorable, for
any $v^{\prime}\in V(H^{\prime})$. Since $H[S]\subseteq H\oplus
H^{\prime}\setminus\\{v^{\prime}\\}$ it can be said $H[S]$ has an $L$-$G$-free
coloring. ∎

######  Claim 8.

$H[V^{\prime\prime}]$ has an $L^{\prime}$-$G$-free coloring.

###### Proof of the Claim8.

By contradiction, let $H[V^{\prime\prime}]$ is not $L^{\prime}$-$G$-free
colorable. Therefore, by Lemma 5, there exists a set $S^{\prime}$ of
$V^{\prime\prime}$, so that $|S^{\prime}|>\delta|L^{\prime}(S^{\prime})|$. In
the other hand, $|L(S\cup
S^{\prime})|=|L(S)|+|L^{\prime}(S^{\prime})|<\frac{1}{\delta}|S+S^{\prime}|$,
therefore, $\delta|L(S\cup S^{\prime})|<|S+S^{\prime}|$ which contradicts to
the maximality of $S$. Hence, $|S^{\prime}|\leq\delta|L^{\prime}(S^{\prime})|$
for each $S^{\prime}\subseteq V^{\prime\prime}$, which means that
$H[V^{\prime\prime}]$ has an $L^{\prime}$-$G$-free coloring. ∎

Therefore, by Claim 7, and Claim 8, we can say that $H\oplus H^{\prime}$ has a
$L$-$G$-free colorable, a contradiction. Hence:

$\chi_{G}^{L}(H\oplus H^{\prime})\leq\chi_{G}^{L}(H)+1.$

Which means that the proof is complete. ∎

In the following, by using Lemma 6, we prove the first main result, namely
Theorem 1.

###### Proof of the Theorem 1.

Without loss of generality (W.l.g), suppose that:

$(|S^{\prime}|-1)(|V(H)|+|S^{\prime}|)\leq|S^{\prime}|\delta(k+1).$

Where $S^{\prime}$ is the maximum subset of $V(H^{\prime})$ so that
$G\nsubseteq H^{\prime}[S^{\prime}]$. Therefore, as $H^{\prime}$ is
$k^{\prime}$-$G$-free choosable and
$\chi_{G}(H^{\prime})\leq\chi_{G}^{L}(H^{\prime})$, so
$\chi_{G}(H^{\prime})\leq k^{\prime}$. For $i=1,2,\ldots,k^{\prime}$, set
$V^{\prime}_{i}\subseteq V(H^{\prime})$ where $V^{\prime}_{1}$ is the maximum
subset of $V(H^{\prime})$ so that $G\nsubseteq H^{\prime}[V_{1}]$ and for each
$i\geq 2$, $V^{\prime}_{i}$ be the maximum subset of
$V(H^{\prime})\setminus(\cup_{j=1}^{j=i-1}V^{\prime}_{j})$, and
$(H^{\prime}\setminus(\cup_{j=1}^{j=i-1}V^{\prime}_{j}))[V^{\prime}_{i}]$ be
$G$-free. It can be said that $|V^{\prime}_{1}|=|S^{\prime}|$, and
$|V^{\prime}_{i}|\leq|V^{\prime}_{i-1}|$ for each $i\geq 2$. So, as
$(|S^{\prime}|-1)(|V(H)|+|S^{\prime}|)\leq|S^{\prime}|\delta(k+1)$,
$S^{\prime}$ is the maximum subset of $V(H^{\prime})$, $G\nsubseteq
H^{\prime}[S^{\prime}]$ and $|V_{1}|=|S^{\prime}|$, then by Lemma 6 we have
the following:

(3) $\chi_{G}^{L}(H\oplus H^{\prime}[V^{\prime}_{1}])\leq\chi_{G}^{L}(H)+1.$

For each $i\geq 1$, set $H_{i}=H_{i-1}\oplus H^{\prime}[V^{\prime}_{i}]$,
where $H_{0}=H$. Therefore, it can be say that the following claim is true:

######  Claim 9.

For each $i\geq 1$, $H\oplus
H^{\prime}[\cup_{j=1}^{j=i}V^{\prime}_{j}]\subseteq H_{i}$.

###### Proof of Claim 9.

It is clear that $V(H\oplus
H^{\prime}[\cup_{j=1}^{j=i}V^{\prime}_{j}])=V(H_{i})$, also one can say that
$E(H\oplus H^{\prime}[\cup_{j=1}^{j=i}V^{\prime}_{j}])=E(H_{i})\setminus
E^{\prime}$, where $E^{\prime}=\\{v_{j}v_{j^{\prime}}~{}:j\leq
j^{\prime},~{}~{}v_{j}\in V^{\prime}_{j},~{}v_{j^{\prime}}\in
V^{\prime}_{j^{\prime}}~{}~{}for~{}each~{}~{}j\leq j^{\prime}\leq i\\}$, which
means that the claim is true. ∎

Also, since
$(|S^{\prime}|-1)(|V(H)|+|S^{\prime}|)\leq|S^{\prime}|\delta(k+1)$,
$|V^{\prime}_{1}|=|S^{\prime}|$, and $|V^{\prime}_{i}|\leq|V^{\prime}_{i-1}|$
for each $i\geq 2$, it can be said that the following claim is true:

######  Claim 10.

For each $i\in\\{1,2,\ldots,k^{\prime}\\}$, we have:

$(|V_{i}^{\prime}|-1)(|V(H)|+|V_{i}^{\prime}|)\leq|V_{i}^{\prime}|\delta(k+1).$

###### Proof of Claim 10.

For $i=1$, since $|V^{\prime}_{1}|=|S^{\prime}|$, and
$(|S^{\prime}|-1)(|V(H)|+|S^{\prime}|)\leq|S^{\prime}|\delta(k+1)$, the proof
is complete. So, suppose that $2\leq j\leq k^{\prime}$, also for each $2\leq
j\leq k^{\prime}$ suppose that $|V^{\prime}_{1}|-|V^{\prime}_{j}|=t_{j}$.
Therefore, we need to show that
$(|V^{\prime}_{j}|-1)(|V(H)|+|V^{\prime}_{j}|)\leq|V^{\prime}_{j}|\delta(k+1)$.
As $|V^{\prime}_{1}|-|V^{\prime}_{j}|=t_{j}$, so:

$(|V^{\prime}_{j}|-1)(|V(H)|+|V^{\prime}_{j}|)=(|V^{\prime}_{1}|-1-t_{j})(|V(H)|+|V^{\prime}_{1}|-t_{j})$

$=(|V^{\prime}_{1}|-1)(|V(H)|+|V^{\prime}_{1}|)-(t_{j}(|V^{\prime}_{1}|-1)-t_{j}(|V(H)|+|V^{\prime}_{1}|-t_{j})$

$\leq(|V^{\prime}_{1}|)\delta(k+1)-(t_{j}(|V^{\prime}_{1}|-1)-t_{j}(|V(H)|+|V^{\prime}_{1}|-t_{j})$

$=(|V^{\prime}_{j}|)\delta(k+1)+t_{j}\delta(k+1)-(t_{j}(|V^{\prime}_{1}|-1)-t_{j}(|V(H)|+|V^{\prime}_{1}|-t_{j})$

$=(|V^{\prime}_{j}|)\delta(k+1)+t_{j}(\delta(k+1)-|V(H)|-2|V^{\prime}_{1}|+1+t_{j})$

$=(|V^{\prime}_{j}|)\delta(k+1)+t_{j}(k\delta+\delta-|V(H)|-|V^{\prime}_{1}|-|V^{\prime}_{j}|+1)$

So for each $j\in\\{2,3,\ldots,k^{\prime}\\}$ we have the following equation:

(4)
$(|V^{\prime}_{j}|-1)(|V(H)|+|V^{\prime}_{j}|)\leq(|V^{\prime}_{j}|)\delta(k+1)+t_{j}(k\delta+\delta-|V(H)|-|V^{\prime}_{1}|-|V^{\prime}_{j}|+1)$

Now by Equation 4, it is sufficient to show that for each
$j\in\\{2,3,\ldots,k^{\prime}\\}$ we have the followings:

$t_{j}(k\delta+\delta-|V(H)|-|V^{\prime}_{1}|-|V^{\prime}_{j}|+1)\leq 0.$

It is easy to say that $|V(H)|\geq(k-1)\delta+1$, also one can say that
$|V^{\prime}_{1}|+|V^{\prime}_{j}|\geq 2\delta$, which means that:

$t_{j}(k\delta+\delta-|V(H)|-|V^{\prime}_{1}|-|V^{\prime}_{j}|+1)\leq 0.$

Hence, for each $i\in\\{1,2,\ldots,k^{\prime}\\}$:

(5)
$(|V_{i}^{\prime}|-1)(|V(H)|+|V_{i}^{\prime}|)\leq|V_{i}^{\prime}|\delta(k+1).$

Therefore, Equation 5 shows that the proof of the claim is complete. ∎

Hence, by Claim 10 and by Lemma 6, for each $i\in\\{1,,\ldots,k^{\prime}\\}$
we can say that:

(6) $\chi_{G}^{L}(H\oplus H^{\prime}[V^{\prime}_{i}])\leq\chi_{G}^{L}(H)+1\leq
k+1.$

So, regarding Equation 6, and
$\chi_{G}(H^{\prime}[\cup_{j=1}^{j=i}V^{\prime}_{j}])=i$, by assigning $i$ new
separate and unique colors to each $V^{\prime}_{i}$, it can concluded that
$\chi_{G}^{L}(H\oplus H^{\prime}[\cup_{j=1}^{j=i}V^{\prime}_{j}])\leq k+i$,
for each $i\in\\{1,2,\ldots,k^{\prime}\\}$. Also, since $H\oplus
H^{\prime}\cong H\oplus H^{\prime}[\cup_{i=1}^{i=k^{\prime}}V^{\prime}_{i}]$,
so:

(7) $\chi_{G}^{L}(H\oplus H^{\prime})=\chi_{G}^{L}(H\oplus
H^{\prime}[\cup_{i=1}^{i=k^{\prime}}V^{\prime}_{i}])\leq
k+k^{\prime}=\chi_{G}^{L}(H)+\chi_{G}^{L}(H^{\prime}).$

Equation 7 means that the proof is complete. ∎

Before proving Theorem 2, we need two lemmas, which we state and prove in the
following. In the following lemma, we determine an upper bond for
$\chi_{G}^{L}(H)$, for each graph $H$ and $G$.

######  Lemma 11.

Suppose that $H$ and $G$ be two graphs, where $\delta(G)=\delta$, $|V(H)|=n$,
then:

$\chi_{G}^{L}(H)\leq\lceil\frac{n}{\delta}\rceil$

###### Proof.

The proof proceeds by induction on $|V(H)|$. It is clear that
$\chi_{G}^{L}(H)\leq\lceil\frac{n}{\delta}\rceil$ when
$|V(H)|\in\\{1,2,\ldots,\delta\\}$. Hence, assume that $|V(H)|\geq\delta+1$
and suppose that $L$ is a $\lceil\frac{n}{\delta}\rceil$-list apportion of
$H$. If there exist $v_{1},v_{2},\ldots,v_{\delta-1}$, and $v_{\delta}$ in $H$
so that $L(v_{1})\cap L(v_{2})\cap\ldots\cap L(v_{\delta})\neq\emptyset$, then
we catch a color $c\in L(v_{1})\cap L(v_{2})\cap\ldots\cap L(v_{\delta})$ and
allocate $c$ to $v_{1},v_{2},\ldots,v_{\delta-1}$, and $v_{\delta}$ and set
$L(v)\setminus\\{c\\}=L(v)$ for any $v\in
V(H)\setminus\\{v_{1},v_{2},\ldots,v_{\delta}\\}$. Regarding
$|L(v)|\geq|L(v)|-1\geq\lceil\frac{n-\delta}{\delta}\rceil$, and by the
induction hypothesis, $H\setminus\\{v_{1},v_{2},\ldots,v_{\delta}\\}$ has an
$L$-$G$-free coloring. Therefore, $H$ is $L$-$G$-free colorable. Otherwise, if
for any $\delta$ vertices $v_{1},v_{2},\ldots,v_{\delta-1}$, and $v_{\delta}$
of $H$, $L(v_{1})\cap L(v_{2})\cap\ldots\cap L(v_{\delta})=\emptyset$, then it
is easy to say that $H$ is $L$-$G$-free colorable, by considering
$\lceil\frac{n}{\delta}\rceil$ class of size at most $\delta$. ∎

Suppose that $H$ and $G$ are two graphs, where $\delta(G)=\delta$, $|V(H)|=n$,
and we may suppose that $g:V(H)\rightarrow\\{1,2,\ldots,\chi_{G}(H)\\}$ is a
$\chi_{G}(H)$-coloring of $H$, so that for each $i\in[\chi_{G}(H)]$,
$G\nsubseteq H[V_{i}]$ and $V_{i}=\\{v\in V(H):~{}~{}g(v)=i\\}$. For each $i$,
suppose that $|V_{i}|=n_{i}$, and w.l.g assume that $n_{1}\geq
n_{2}\geq\ldots\geq n_{\chi_{G}(H)}$. It is easy to say that $n_{i}\geq\delta$
for each $i\in[\chi_{G}(H)-1]$. Now by considering $n_{i}$, we have the
following lemma.

######  Lemma 12.

If $(n_{1}-1)|V(H)|\leq n_{1}\delta\chi_{G}(H)$. Then:

$\chi_{G}^{L}(H)=\chi_{G}(H).$

###### Proof.

Since $\chi_{G}(H)\leq\chi_{G}^{L}(H)$, it do to prove that $H$ is
$\chi_{G}(H)$-$G$-free choosable(list colorable). The proof proceeds by
induction on $\chi_{G}(H)$. If $H$ be $G$-free, then
$\chi_{G}^{L}(H)=\chi_{G}(H)=1$, so suppose that $H$ has at least one copy of
$G$ as a subgraph, that is $2\leq\chi_{G}(H)$. Since $n_{1}\geq\delta$, then
by lemma assumption one can say that:

(8) $|V(H)|\leq\frac{n_{1}\delta}{n_{1}-1}\chi_{G}(H).$

If $n_{1}=\delta$, then as $n_{1}$ is maximal, so
$\chi_{G}(H)=\lceil\frac{|V(H)|}{\delta}\rceil$, hence by Lemma 11,
$\chi_{G}^{L}(H)=\chi_{G}(H)$. Now, suppose that $n_{1}\geq\delta+1$. Hence:

$|V(H)\setminus V_{1}|=|V(H)|-n_{1}$
$\leq\frac{n_{1}\delta}{n_{1}-1}\chi_{G}(H)-n_{1}$
$=\frac{n_{1}}{n_{1}-1}(\delta\chi_{G}(H)-n_{1}+1)$
$\leq\frac{n_{1}}{n_{1}-1}(\delta\chi_{G}(H)-\delta)$
$\leq\frac{n_{2}\delta}{n_{2}-1}(\chi_{G}(H)-1)$

So, this inequality and induction hypothesis implies that $H\setminus V_{1}$
is $(\chi_{G}(H)-1)$-$G$-free choosable, because $V_{2}$ is the maximal color
class of $H\setminus V_{1}$. Now, regarding Equation 8 and the fact that
$H\setminus V_{1}$ is $(\chi_{G}(H)-1)$-$G$-free list colorable, Lemma 6
implies that $H$ is $\chi_{G}(H)$-$G$-free choosable, which means that the
proof is complete. ∎

In the following, we prove Theorem 2 and Theorem 3 by using Lemma 12.

######  Theorem 13.

(Theorem2) Suppose that $H$ and $G$ are two graphs, where $\delta(G)=\delta$.
If we have, $|V(H)|\leq\delta\chi_{G}(H)+\sqrt{\delta\chi_{G}(H)}-(\delta-1)$,
then:

$\chi_{G}^{L}(H)=\chi_{G}(H).$

###### Proof.

Assume that $g:V(H)\rightarrow\\{1,2,\ldots,\chi_{G}(H)\\}$ is the
$\chi_{G}(H)$-coloring of $H$, so that for each $i\in[\chi_{G}(H)]$,
$G\nsubseteq H[V_{i}]$ and $V_{i}=\\{v\in V(H):~{}~{}g(v)=i\\}$. For each $i$,
suppose that $|V_{i}|=n_{i}$, and w.l.g assume that $n_{1}\geq
n_{2}\geq\ldots\geq n_{\chi_{G}(H)}$. It is easy to say that $n_{i}\geq\delta$
for each $i\in[\chi_{G}(H)-1]$, and $n_{\chi_{G}(H)}\geq 1$. It can be checked
that:

(9) $n_{1}\leq|V(H)|-(\delta\chi_{G}(H)-(2\delta-1)).$

Otherwise one can check that $\sum_{i=1}^{i=\chi_{G}(H)}n_{i}\geq|V(H)|+1$, a
contradiction. Therefore, by assumption lemma and by Equation 9 we have the
next equation:

(10)
$n_{1}\leq\delta\chi_{G}(H)+\sqrt{\delta\chi_{G}(H)}-(\delta-1)-(\delta\chi_{G}(H)-(2\delta-1))=\sqrt{\delta\chi_{G}(H)}+\delta.$

Hence, by Equation 10 we have the following:

$\frac{n_{1}}{n_{1}-1}\delta\chi_{G}(H)\geq\frac{\sqrt{\delta\chi_{G}(H)}+\delta}{\sqrt{\delta\chi_{G}(H)}+(\delta-1)}\times\delta\chi_{G}(H)$
$=\delta\chi_{G}(H)+\frac{\delta\chi_{G}(H)}{\sqrt{\delta\chi_{G}(H)}+(\delta-1)}$
$>\delta\chi_{G}(H)+\frac{\delta\chi_{G}(H)-(\delta-1)}{\sqrt{\delta\chi_{G}(H)}+(\delta-1)}$
$=\delta\chi_{G}(H)+\sqrt{\delta\chi_{G}(H)}-(\delta-1)\geq|V(H)|$

So, by Lemma 12, $\chi_{G}^{L}(H)=\chi_{G}(H)$, which means that the proof is
complete. ∎

Now by Theorem 13, one can say that the following results are valid. For this,
first we need the following definition.

######  Definition 14.

$\operatorname{\mathcal{G}}$-free graph: Suppose that
$\operatorname{\mathcal{G}}$ is a collection of some graphs, a given graph $H$
is called $\operatorname{\mathcal{G}}$-free, if $H$ contains no copy of $G$ as
a subgraph for each $G\in\operatorname{\mathcal{G}}$. When
$\operatorname{\mathcal{G}}=\\{G\\}$, then $H$ is $G$-free if $G\nsubseteq H$.
In this attention, we say a graph $H$ has a
$k$-$\operatorname{\mathcal{G}}$-free coloring if there exists a map
$g:V(H)\longrightarrow\\{1,\ldots,k\\}$ so that each of the color classes of
$g$ is $\operatorname{\mathcal{G}}$-free i.e. contain no copy of each member
of $\operatorname{\mathcal{G}}$ as a subgraph. For given graphs $H$ and
$\operatorname{\mathcal{G}}$, the $\chi_{\operatorname{\mathcal{G}}}(H)$ of
$H$ is the minimum integer $k$ so that $H$ is
$k$-$\operatorname{\mathcal{G}}$-free coloring.

######  Corollary 15.

Suppose that $\operatorname{\mathcal{G}}$ be a collection of all $d$-regular
graphs, where for each $G\in\operatorname{\mathcal{G}}$ we have:

$|V(H)|\leq d\chi_{G}(H)+\sqrt{d\chi_{G}(H)}-(d-1).$

Then:

$\chi_{\operatorname{\mathcal{G}}}^{L}(H)=\chi_{\operatorname{\mathcal{G}}}(H).$

###### Proof.

Consider $G\in\operatorname{\mathcal{G}}$, so that for which
$\chi_{G^{\prime}}(H)\leq\chi_{G}(H)$ for each
$G^{\prime}\in\operatorname{\mathcal{G}}$. Therefore, one can say that
$\chi_{\operatorname{\mathcal{G}}}(H)\leq\chi_{G}(H)$, also by assumption and
by Theorem 13 we have $\chi_{G}(H)=\chi^{L}_{G}(H)$, that is
$\chi_{\operatorname{\mathcal{G}}}(H)\leq\chi^{L}_{G}(H)$. So as
$\chi^{L}_{G}(H)\leq\chi^{L}_{\operatorname{\mathcal{G}}}(H)$ we have
$\chi_{\operatorname{\mathcal{G}}}(H)\leq\chi^{L}_{\operatorname{\mathcal{G}}}(H)$.
Now we have to show that
$\chi^{L}_{\operatorname{\mathcal{G}}}(H)\leq\chi_{\operatorname{\mathcal{G}}}(H)$.
Consider $G^{\prime\prime}\in\operatorname{\mathcal{G}}$, so that for which
$\chi^{L}_{\operatorname{\mathcal{G}}}(H)\leq\chi^{L}_{G^{\prime\prime}}(H)$.
Therefore, by assumption and by Theorem 13, we have
$\chi_{G^{\prime\prime}}(H)=\chi^{L}_{G^{\prime\prime}}(H)$, and as
$\chi_{G^{\prime\prime}}(H)\leq\chi_{\operatorname{\mathcal{G}}}(H)$, it can
be said that
$\chi^{L}_{\operatorname{\mathcal{G}}}(H)\leq\chi_{\operatorname{\mathcal{G}}}(H)$,
which means that the proof is complete. ∎

In corollary 15, if we take $d=2$ hence
$\operatorname{\mathcal{G}}=\\{C_{n},n\geq 3\\}$ and for any arbitrary graph
for $H$, then it is easy to say that we get Theorem C. Also, for $d=1$, we
have $\operatorname{\mathcal{G}}=\\{K_{2}\\}$. Hence, as
$|V(H)|\leq\chi(H)+\sqrt{\chi(H)}\leq\chi(H)+\sqrt{2\chi(H)}$, therefore by
corollary 15, if we take $d=1$, then we get Theorem A.

######  Theorem 16.

(Theorem 3) For each two connected graphs $H$ and $G$, we have:

$\chi^{L}_{{}_{G}}(H)\leq\lceil\frac{\Delta(H)}{\delta(G)}\rceil+1.$

###### Proof.

Suppose that $H$ and $G$ are two connected graphs that satisfy the theorem
conditions. Assume that $L$ is a $k$-list assignment of $H$, where
$k=\lceil\frac{\Delta(H)}{\delta(G)}\rceil+1$. Suppose that $H$ is not
$G$-free. Otherwise, it is easy to say that
$\chi^{L}_{{}_{G}}(H)=1\leq\lceil\frac{\Delta(H)}{\delta(G)}\rceil+1$. Hence
assume that $G\subseteq H$, that is $2\leq\chi_{{}_{G}}(H)$. Suppose that
$v_{1},v_{2},\ldots,v_{n}$ be an ordering of $V(H)$ so that for each $i$,
vertex $v_{i}$, have at most $\Delta(H)$ low-indexed neighbors in $H$. Now we
color the vertices of $H$ from their lists by this order. Assume that
$v_{1},v_{2},\ldots,v_{i}$ has been colored and every subset of
$v_{1},v_{2},\ldots,v_{i}$ which colored with the same color be $G$-free.
Since $v_{i+1}$ has at most $\Delta(H)+1-\delta(G)$ neighbors in
$v_{1},v_{2},\ldots,v_{i}$, there are at most
$\lceil\frac{\Delta(H)}{\delta(G)}\rceil$ of this $G$ containing at least
$\delta$ neighbors of $v_{i+1}$. Therefore, it can be said that for $v_{i+1}$,
there exists at least one color available in $L(v_{i+1})$ which appears at
most once among the low-indexed neighbor of $v_{i+1}$. We assign such color to
$v_{i+1}$. Therefore, we gain a $G$-free coloring of
$H[{v_{1},v_{2},\ldots,v_{i+1}}]$. By continuing this method until $i+1=n$, we
obtain a $G$-free $L$-coloring of $H$. ∎

###  2.1. Proof of Theorem 4

Before proving Theorem 4, we need to some results. Suppose that
$\operatorname{\mathbb{R}}$ is a collection of all $d$-regular graphs and let
$H$ be an arbitrary graph. Hence, we have the following lemma:

######  Lemma 17.

Suppose that $n$ be a positive integer, and $H$ be an arbitrary graph. So:

$\chi_{\operatorname{\mathbb{R}}}(H\oplus
K_{n})\geq\frac{\chi_{\operatorname{\mathbb{R}}}(H)+n}{d}.$

###### Proof.

Suppose that $t=\chi_{\operatorname{\mathbb{R}}}(H\oplus K_{n})$ and let $g$
be a $t$-$\operatorname{\mathcal{G}}$-free coloring of $H\oplus K_{n}$. For
each $i\in\\{1,2,\ldots,\chi_{\operatorname{\mathbb{R}}}(H)\\}$, let:

$V_{i}=\\{v\in V(H\oplus K_{n})~{}:~{}g(v)=i\\}.$

Since $H[V_{i}]$ is a $\operatorname{\mathbb{R}}$-free, and
$\operatorname{\mathbb{R}}$ is a collection of all $d$-regular graphs, so
$K_{d+1}\nsubseteq H[V_{i}]$ for each $i$. Therefore, each $V_{i}$ contains at
most $d$ vertices of $V(K_{n})$. Now, if $t_{j}=|\\{i~{}:~{}1\leq i\leq
t~{}~{}and~{}~{}|V_{i}\cap V(K_{n})|=j\\}|$, and $k_{j}\neq 0$, then $j\leq
d$. Therefore, $t=t_{0}+t_{1}+\ldots+t_{d}$, and it is easy to say that
$n=\sum_{m=1}^{m=d}mt_{m}$, also one can say that
$\chi_{\operatorname{\mathbb{R}}}(H)\leq\sum_{m=0}^{m=d-1}t_{m}$. Hence,

$dt=d(\sum_{m=0}^{m=d}t_{m})=dt_{0}+\sum_{m=1}^{m=d-1}(d-m)t_{m}+\sum_{m=1}^{m=d}mt_{m}$
$\geq(d-1)t_{0}+\sum_{m=0}^{m=d-1}t_{m}+\sum_{m=1}^{m=d}mt_{m}$
$\geq\chi_{\operatorname{\mathbb{R}}}(H)+n$

Therefore, $t=\chi_{\operatorname{\mathbb{R}}}(H\oplus
K_{n})\geq\frac{\chi_{\operatorname{\mathbb{R}}}(H)+n}{d}$, which means that
proof is complete. ∎

######  Theorem 18.

Assume that $\operatorname{\mathbb{R}}$ is a collection of all $d$-regular
graphs where $d\geq 1$. For each arbitrary graph $H$, there exists a non-
negative integer $n^{\prime}$, so that
$\chi_{\operatorname{\mathbb{R}}}(H\oplus
K_{n})=\chi^{L}_{\operatorname{\mathbb{R}}}(H\oplus K_{n})$, for any integer
$n$ with $n\geq n^{\prime}$.

###### Proof.

Suppose that $m=|V(H)|$, and
$g:V(H)\rightarrow\\{1,2,\ldots,\chi_{\operatorname{\mathbb{R}}}(H\oplus
K_{n})\\}$ be an optimal $\operatorname{\mathbb{R}}$-free coloring of $H\oplus
K_{n}$, with a color class of sizes $n_{1}\geq n_{2}\geq\ldots\geq
n_{\chi_{\operatorname{\mathbb{R}}}(H\oplus K_{n})}$. One can check that
$d\leq n_{1}\leq m+d$ for sufficiently large $n$. By Lemma 17,
$\chi_{\operatorname{\mathbb{R}}}(H\oplus
K_{n})\geq\frac{\chi_{\operatorname{\mathbb{R}}}(H)+n}{d}$. Observe that
$m+n\leq\frac{d(m+d)}{m+d-1}\frac{dn_{1}}{n_{1}+1-d}\leq\frac{dn_{1}}{n_{1}+1-d}\chi_{\operatorname{\mathbb{R}}}(H\oplus
K_{n})$ for sufficiently large $n$. Therefore,

$(n_{1}+1-d)(m+n)\leq dn_{1}\chi_{\operatorname{\mathbb{R}}}(H\oplus K_{n})$

Hence, by Lemma 12, $\chi_{\operatorname{\mathbb{R}}}(H\oplus
K_{n})=\chi^{L}_{\operatorname{\mathbb{R}}}(H\oplus K_{n})$, which means that
the proof is complete. ∎

The following theorem has been proved by Ohba [9]:

######  Theorem 19.

[9] Let $H$ be a graph. Hence there is a positive integer $n^{\prime}$ so that
$\chi(H\oplus K_{n})=\chi_{L}(H\oplus K_{n})$, for each integer $n$ with
$n^{\prime}\leq n$.

As a generalized result of Theorem 19, Lingyan Zhe, and Baoyindureng Wu have
proven the following theorem [13].

######  Theorem 20.

[13] Let $H$ be a graph. Hence there is a positive integer $n^{\prime}$ so
that $\alpha(H\oplus K_{n})=\alpha_{L}(H\oplus K_{n})$, for each integer $n$
with $n^{\prime}\leq n$.

In Theorem 18, if we take $d=1$ hence $\operatorname{\mathbb{R}}=\\{K_{2}\\}$,
then we get Theorem 19. Also, by setting $d=2$, we have
$\operatorname{\mathbb{R}}=\\{C_{n},n\geq 3\\}$ and for any arbitrary graph
for $H$, then it is easy to say that we get Theorem 20.

###  2.2.  Some research problems related to the contents of this paper.

In this section, we propose some research problems related to the contents of
this paper. The following conjecture has been proposed by Ohba [9]:

######  Conjecture 1.

[9] If $|V(H)|\leq 2\chi(H)+1$, then:

$\chi_{L}(H)=\chi(H).$

Jonathan A. Noel et.al in [8] have proven the conjecture1. The first problem
concerns Theorem 2 and Conjecture 1, as we address below:

######  Problem 20.1.

For each two connected graphs $H$ and $G$, find a constant $M$, so that if
$|V(H)|\leq M\chi_{G}(H)$, Then:

$\chi^{L}_{G}(H)=\chi_{G}(H).$

Y.Rowshan and A.Taherkhani in [10] have proven the following theorem.

######  Theorem D.

Suppose that $H$ and $G$ be two connected graphs while $H$ satisfies the
followinf items:

  * •

If $G$ is regular, then $H\ncong G$.

  * •

If $G\cong K_{\delta(G)+1}$, then $H$ is not $K_{k\delta(G)+1}$.

  * •

If $G\cong K_{2}$, then $H$ is neither a complete graph nor an odd cycle.

Then:

$\chi_{{}_{G}}(H)\leq\lceil\frac{\Delta(H)}{\delta(G)}\rceil.$

And one of those color classes is a maximum induced $G$-free subgraph in $H$.

The second problem concerns Theorem 3 and D, as we address below:

######  Problem 20.2.

Suppose that $H$ and $G$ be two connected graphs while $H$ satisfies the
following items:

  * •

If $G$ is regular, then $H\ncong G$.

  * •

If $G\cong K_{\delta(G)+1}$, then $H$ is not $K_{k\delta(G)+1}$.

  * •

If $G\cong K_{2}$, then $H$ is neither a complete graph nor an odd cycle.

Then:

$\chi^{L}_{{}_{G}}(H)\leq\lceil\frac{\Delta(H)}{\delta(G)}\rceil.$

And one of those color classes is a maximum induced $G$-free subgraph in $H$.

## References

  * [1] Gary Chartrand, Hudson V. Kronk, and Curtiss E. Wall.  The point-arboricity of a graph.  Israel J. Math., 6:169–175, 1968.
  * [2] Frank Harary.  Conditional colorability in graphs.  In Graphs and applications (Boulder, Colo., 1982), Wiley-Intersci. Publ., pages 127–136. Wiley, New York, 1985.
  * [3] Stephen Hedetniemi.  On partitioning planar graphs.  Canad. Math. Bull., 11:203–211, 1968.
  * [4] Hal A Kierstead, Andrew Salmon, and Ran Wang.  On the choice number of complete multipartite graphs with part size four.  European Journal of Combinatorics, 58:1–16, 2016.
  * [5] Jakub Kozik, Piotr Micek, and Xuding Zhu.  Towards an on-line version of ohba’s conjecture.  European Journal of Combinatorics, 36:110–121, 2014.
  * [6] Hudson V. Kronk and John Mitchem.  Critical point-arboritic graphs.  J. London Math. Soc. (2), 9:459–466, 1974/75.
  * [7] Jeffrey Allen Mudrock.  On the list coloring problem and its equitable variants.  PhD thesis, Illinois Institute of Technology, 2018.
  * [8] Jonathan A Noel, Bruce A Reed, and Hehui Wu.  A proof of a conjecture of ohba.  Journal of Graph Theory, 79(2):86–102, 2015.
  * [9] Kyoji Ohba.  On chromatic-choosable graphs.  Journal of Graph Theory, 40(2):130–135, 2002.
  * [10] Yaser Rowshan and Ali Taherkhani.  A catlin-type theorem for graph partitioning avoiding prescribed subgraphs.  arXiv preprint arXiv:2002.04702, 2020.
  * [11] Rongxing Xu, Yeong-Nan Yeh, and Xuding Zhu.  List colouring of graphs and generalized dyck paths.  Discrete Mathematics, 341(3):810–819, 2018.
  * [12] Nini Xue and Baoyindureng Wu.  List point arboricity of graphs.  Discrete Mathematics, Algorithms and Applications, 4(02):1250027, 2012.
  * [13] Lingyan Zhen and Baoyindureng Wu.  List point arboricity of dense graphs.  Graphs and Combinatorics, 25(1):123–128, 2009.
  * [14] Jialu Zhu and Xuding Zhu.  Chromatic $\lambda$-choosable and $\lambda$-paintable graphs.  Journal of Graph Theory, 98(4):642–652, 2021.