\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{amsthm,amsmath,amssymb}
\usepackage{graphicx}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\sloppy



\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}

 \title{\bf Some results on chromaticity of quasi-linear paths and cycles}


\author{
Ioan Tomescu\\
\small Faculty of Mathematics and Computer Science\\[-0.8ex]
\small University of Bucharest\\[-0.8ex]
\small Bucharest, Romania\\ 
\small and\\
\small Abdus Salam School of Mathematical Sciences\\[-0.8ex]
\small GC University, Lahore, Pakistan\\
\small\tt ioan@fmi.unibuc.ro\\}

\date{\dateline{XX}{XX}\\
\small Mathematics Subject Classifications: 05C15, 05C65}

\begin{document}

\maketitle



\begin{abstract}
Let $r\geq 1$ be an integer. An $h$-hypergraph $H$ is said to be $r$-quasi-linear (linear for $r=1$) if any two edges of $H$ intersect in 0 or $r$ vertices. In this paper it is shown that $r$-quasi-linear paths $P_{m}^{h,r}$ of length $m\geq 1$ and cycles $C_{m}^{h,r}$ of length $m\geq 3$ are chromatically unique in the set of $h$-uniform $r$-quasi-linear hypergraphs provided $r\geq 2$ and $h\geq 3r-1$.

\bigskip\noindent\textbf{Keywords:} quasi-linear hypergraph; sunflower hypergraph; quasi-linear path; quasi-linear cycle; chromatic polynomial; chromatic uniqueness; potential function
\end{abstract}


\section{ Notation and preliminary results}
 A simple hypergraph $H=(V,{\cal E})$, with order $n=|V|$ and size $m=|{\cal E}|$,
consists of a vertex-set $V(H)=V$ and an edge-set $E(H)={\cal E}$, where $E
\subseteq V$ and $|E|\geq 2$ for each edge $E$ in ${\cal E}$. $H$ is $h$-uniform, or is
an $h$-hypergraph, if $|E|=h$ for each $E$ in ${\cal E}$ and $H$ is linear
if no two edges intersect in more than one vertex [1]. $H$ is said to be antilinear if for every two edges $E,F$ of $H$ we have $|E\cap F|\neq 1$. Let $r\geq 1$ and $h\geq 2r+1$. $H$ is said to be $r$-quasi-linear (or shortly quasi-linear) [13] if any two edges intersect in 0 or $r$ vertices. Examples of quasi-linear hypergraphs are $t$-stars [5, 8], also called sunflower hypergraphs [7, 11, 12].
We say that a hypergraph $S$ is a $t$-star with kernel $K$ where $K\subseteq V(S)$ and $t\geq 1$ if $S$ has exactly $t$ edges and $e\cap e'=K$ for all distinct edges $e$ and $e'$ of $S$. A system of $t$ pairwise disjoint edges (matching) is a $t$-star with empty kernel. In [12] a sunflower hypergraph was denoted by $SH(n,p,h)$; it is an $h$-hypergraph having a kernel of cardinality $h-p$, $n$ vertices and $k$ edges, where
$n=h+(k-1)p$ and $1\leq p\leq h-1$.\\
A hypergraph for which no edge is a subset of any other is called Sperner.
Two vertices $u,v\in V(H)$ belong to the same component if there are vertices $x_{0}=u,x_{1},\ldots ,x_{k}=v$
and edges $E_{1},\ldots ,E_{k}$ of $H$ such that $x_{i-1}$, $x_{i}\in E_{i}$
for each $i$ $(1\leq i\leq k)$ [1].
$H$ is said to be connected if it has only one component.
 An $h$-uniform hypertree is a connected linear $h$-hypergraph without
cycles. We shall define two classes of quasi-linear uniform hypergraphs called 
quasi-linear elementary paths and quasi-linear elementary cycles and denoted by $P_{m}^{h,r}$ and $C_{m}^{h,r}$, respectively, as follows:
$P_{m}^{h,r}$ consists of $m$ edges $E_1,\ldots ,E_m$ such that $|E_1|=\ldots =|E_m|=h, |E_k\cap E_l|=r$  if $\{k,l\}=\{i,i+1\}$ for any $1\leq i\leq m-1$ and 0 otherwise. Cycles $C_{m}^{h,r}$ are defined analogously, by also imposing $|E_m\cap E_1|=r$.
\par
If $\lambda \in \mathbb{N}$, a
$\lambda$-coloring of a hypergraph $H$ is a function $f: V(H)\rightarrow
\{1,\ldots ,\lambda \}$ such that for each edge $E$ of $H$ there exist $x$, $y$
in $E$ for which $f(x)\neq f(y)$. The number of $\lambda$-colorings of $H$ is given
by a polynomial $P(H,\lambda)$ of degree $|V(H)|$ in $\lambda$, called the
chromatic polynomial of $H$.
$P(H,\lambda)$ can be obtained applying inclusion-exclusion principle, in the same way as for graphs, getting the following formula:
\begin{equation}
P(H,\lambda )= \sum _{W\subseteq E(H)}(-1)^{|W|}\lambda ^{c(W)},
\end{equation}
where $c(W)$ denotes the number of components of the spanning subhypergraph induced by the edges from $W$. By rearranging terms in (1) we obtain that if $H$ has order $n$ then
$P(H,\lambda)=\lambda ^{n}+a_{n-1}\lambda^{n-1}+\ldots +a_1\lambda $, where
\begin{equation}
a_i=\sum_{j\geq 0}(-1)^{j}N(i,j)
\end{equation}
and $N(i,j)$ denotes the number of spanning subhypergraphs of $H$ with $n$ vertices, $i$ components and $j$ edges [10].\\
All $h$-uniform hypertrees have the same chromatic polynomial.
\begin{lemma}
{\rm [6]}. If $T_{k}^{h}$ is any $h$-uniform hypertree with $k$ edges, then
\begin{equation}
P(T_{k}^{h},\lambda )=\lambda (\lambda ^{h-1}-1)^{k}.
\end{equation}
\end{lemma}
Two hypergraphs $H$ and $G$ are said to be chromatically equivalent or $\chi$-equivalent,
written $H\sim G$, if $P(H,\lambda)=P(G,\lambda)$.
Let us restrict ourselves to the class of Sperner hypergraphs.
A simple hypergraph $H$ is said to be chromatically
unique if $H$ is isomorphic to $H'$ for every simple hypergraph $H'$ such that
$H'\sim H$; that is, the structure of $H$ is uniquely determined up to isomorphism
by its chromatic polynomial. The notion of $\chi$-unique graphs was first introduced
and studied by Chao and Whitehead [4] (see also [9]).
It is clear that all $h$-hypergraphs are Sperner. The notion of $\chi $-uniqueness
in the class of $h$-hypergraphs may be defined as follows: An $h$-hypergraph $H$ is said
to be $h$-chromatically unique if $H$ is isomorphic to $H'$ for every $h$-hypergraph
$H'$ such that $H'\sim H$.
\par
Non-trivial chromatically unique hypergraphs are extremely rare.
One example of a non-trivial chromatically unique hypergraph was proposed by Borowiecki and Lazuka; it is $SH(n,1,h)$.
\begin{theorem} {\rm [3]}
$SH(n,1,h)$ is chromatically unique.
\end{theorem}
The proof of this result was completed in [11].
Note that for $p=h-1$, $SH(n,h-1,h)$ is an $h$-uniform hypertree.
The chromaticity of $SH(n,p,h)$ may be stated as follows. 
\begin{theorem} {\rm [12]}
 Let $n=h+(k-1)p$, where $h\geq 3$, $k\geq 1$ and $1\leq p\leq h-1$. Then
SH(n,p,h) is $h$-chromatically unique for every $1\leq p\leq h-2$; for $p=h-1$
$SH(n,h-1,h)$ is $h$-chromatically unique for $k=1$ or $k=2$ but it has not
this property for $k\geq 3$. Moreover, $SH(n,p,h)$ is not chromatically unique for every $p,k\geq 2$.
\end{theorem}
$SH(n,p,h)$ is quasi-linear with $r=h-p$ and it is a path for $k=2$.\\
Since $P_{2}^{h,r}$ is a sunflower hypergraph $SH(n,p,h)$ with $p=h-r$ having $k=2$ edges, from Theorem 1.3 it follows that $P_{2}^{h,r}$ is $h$-chromatically unique for every $1\leq r\leq h-1$. Also $P_{m}^{h,1}$ is an $h$-uniform hypertree, hence for $m\geq 3$ it is not $h$-chromatically unique. We shall prove that $P_{m}^{h,r}$ for every $m\geq 1$ and $C_{m}^{h,r}$ for every $m\geq 3$ are $h$-chromatically unique hypergraphs in the set of quasi-linear hypergraphs provided $r\geq 2$ and $h\geq 3r-1$.
In [10] it was shown that $C_{m}^{h,r}$ is $h$-chromatically unique for $r=1$ and every $m,h\geq 3$, but it is not chromatically unique for $r=1$ and $m,h\geq 3$ [2].
The chromaticity of non-uniform hypertrees was studied by Walter [15].

\section{Main results}
We need the following result about the first coefficients of the chromatic polynomial of a quasi-linear $h$-hypergraph with a particular structure relatively to subhypergraphs induced by 3 edges.
\begin{lemma}
Let $r\geq 2$, $h\geq 2r+1$ and $H$ be a quasi-linear $h$-hypergraph of order $n$ and size $m$ having the property that all subhypergraphs induced by $3$ edges have one of the following patterns:\\
$a) P_{3}^{h,r}$; $b) P_{2}^{h,r}$ and an isolated edge, or $c)\, \,3$ isolated edges. Then
\begin{equation}
P(H,\lambda)= \lambda ^{n}-m\lambda ^{n-h+1}+\beta _{1}\lambda ^{n-2h+r+1}+
\beta _{2}\lambda ^{n-2h+2}-\beta _{3}\lambda ^{n-3h+2r+1}+R(\lambda ),
\end{equation}
where $R(\lambda )$ is a polynomial in $\lambda $ of degree at most equal to $n-3h+2r$, $\beta _{2}$ is the number of pairwise disjoint edges of $H$ and $\beta _{1}$ and $\beta _{3}$ are the numbers of induced subhypergraphs of $H$ isomorphic to $P_{2}^{h,r}$ and $P_{3}^{h,r}$, respectively.
\end{lemma}
\begin{proof}
By the hypothesis we have $n-h+1>n-2h+r+1>n-2h+2>n-3h+2r+1$. If $W\subset E(H)$ in (1) consists of one edge we get $N(n-h+1,j)=m$ if $j=1$ and $N(n-h+1,j)=0$ otherwise.\\
If $|W|=2$ then $N(n-2h+r+1,2)$ and $N(n-2h+2,2)$ count the number of unordered pairs $\{E,F\}$ of edges such that $|E\cap F|=r$ and $E\cap F=\emptyset$, respectively.
In these two cases suppose that there exists an edge $G\in \mathcal{E}$, $G\neq E,F$, such that $G\subset E\cup F$. Denote $i=|G\cap E\cap F|$. It follows that $0\leq i\leq r$,
$|G\cap (E\backslash F)|=r-i$, $|G\cap (F\backslash E)|=r-i$, thus yielding $h=|G|=2r-i\leq 2r$, which contradicts the hypothesis. It follows that $N(n-2h+r+1,j)=N(n-2h+2,j)=0$ for every $j\neq 2$ and $\beta _{1},\beta _{2}$ represent the numbers of induced subhypergraphs of $H$ consisting of $P_{2}^{h,r}$ and of an unordered pair of disjoint edges, respectively.\\
Similarly, if $|W|=3$, by the hypoyhesis 3 edges can induce only subhypergraphs of types a), b) or c). We obtain that $N(n-3h+2r+1),N(n-3h+r+2,3)$ and $N(n-3h+3,3)$ count the subhypergraphs of $H$ induced by an unordered triple of edges $\{D,E,F\}$ such that these subhypergraphs are isomorphic to $P_{3}^{h,r}$, $P_{2}^{h,r}$ and an isolated edge and 3 isolated edges, respectively. We also have $n-3h+2r+1>n-3h+r+2>n-3h+3$ since $r\geq 2$ and $N(n-3h+2r+1,j)=0$ for every $0\leq j\leq 2$.\\
If the edges $D,E,F$ of $H$ induce a $P_{3}^{h,r}$, where $D\cap F=\emptyset $, suppose that there exists an edge $G\neq D,E,F$ such that $G\subset D\cup E\cup F$. We have proved that $G\not \subset E\cup F$, thus implying $G\cap D\neq \emptyset$; similarly $G\not \subset D\cup F$ implies $G\cap E\neq \emptyset$. We have found 3 edges $D,E,G$ such that $D\cap E\neq \emptyset,D\cap G\neq \emptyset$ and $E\cap G\neq \emptyset$, which contradicts the hypothesis. This implies that $N(n-3h+2r+1,j)=0$ for every $j\geq 4$. Since by adding new edges to $W$ the number of components $c(W)$ decreases, it follows that $P(H,\lambda)$ is given by (4), where $\beta _{3}$ is the number of induced subhypergraphs of $H$ isomorphic to $P_{3}^{h,r}$.
\end{proof}
\begin{theorem}
Let $H$ be an antilinear $h$-hypergraph such that $P(H,\lambda)=P(G,\lambda)$, where $G$ is $P_{m}^{h,r} (m\geq 1)$ or $C_{m}^{h,r} (m\geq 3)$. If $r\geq 2$ and
$h\geq 3r-1$ then $H$ is isomorphic to $G$.
\end{theorem}
\begin{proof}
It is trivial to see that $P_{m}^{h,r}$ for $1\leq m\leq 3$ and $C_{3}^{h,r}$ are $h$-chromatically unique. Let $m\geq 4$. We shall consider two subcases:\\ I. $G=P_{m}^{h,r}$ and II. $G=C_{m}^{h,r}$.\\
I. Let $H$ be an antilinear $h$-hypergraph such that $P(H,\lambda)=P(P_{m}^{h,r},\lambda)$.\\ The order of an hypergraph is being determined by the leading term of the chromatic polynomial, it follows that $H$ has order $n=h+(m-1)(h-r)$. From (2) one deduces that
\begin{equation}
P(P_{m}^{h,r},\lambda)=\lambda ^{n}-m\lambda ^{n-h+1}+\alpha _{1}\lambda ^{n-2h+r+1}+\alpha _{2}\lambda ^{n-2h+2}-\alpha _{3}\lambda ^{n-3h+2r+1}+Q(\lambda),
\end{equation}
where $Q(\lambda)$ is a polynomial of degree at most equal to $n-3h+r+2$, $\alpha _{1}=m-1$ is the number of subpaths $P_{2}^{h,r}$ of length two, $\alpha _{2}={{m}\choose{2}}-m+1$ is the number of pairs of pairwise disjoint edges and $\alpha _{3}=m-2$ is the number of subpaths $P_{3}^{h,r}$ of length three in $P_{m}^{h,r}$. Also since any spanning subhypergraph of $P_{m}^{h,r}$ induced by less than $m$ edges is not connected, it follows that in (5) the coefficient of $\lambda$ is $(-1)^{m}$, which implies that $H$ is also connected [15].\\
Since $H$ has all edges of cardinality $h$, it follows that the number of components of a spanning subhypergraph of $H$ may be $n,n-h+1$ or a smaller number. Any spanning subhypergraph of $H$ with $n$ vertices and $n-h+1$ components must contain only one edge. From (2) we deduce that $a_{n-h+1}=-N(n-h+1,1)=-|E(H)|$, hence $H$ has exactly $m$ edges. Every spanning subhypergraph of $H$ with $n$ vertices has two kinds of components: isolated vertices and components including at least $h$ vertices. The components including at least $h$ vertices will be called major components [10].\\ If such a spanning subhypergraph has at least two major components then it contains at most $n-2h+2$ components and this bound is reached when the major components are two disjoint edges and minor components are $n-2h$ isolated vertices. It follows that all coefficients $a_{n-h+1},\ldots ,a_{n-2h+r+1}$ given by (2) correspond to the case when all spanning subhypergraphs of $H$ of order $n$ contain only one major component. In this way $N(n-h,j)$ counts the spanning subhypergraphs of $H$ consisting of a subset $Y$ of vertices (the major component) and $n-h-1$ isolated vertices, where $Y\subset V(H), |Y|=h+1$.\\
Denote by $\varphi (Y)$ the number of edges included in $Y$. Because $Y$ induces a component having $h+1$ vertices, it follows that $\varphi (Y)\geq 2$ and for each $i\geq 2$  the union of any $i$ edges included in $Y$ equals $Y$. Since $N(n-h,0)=N(n-h,1)=0$, by (2) we get
$$ a_{n-h}=\sum _{j\geq 2}(-1)^{j}N(n-h,j)=\sum _{j\geq 2}(-1)^{j}\sum _{|Y|=h+1 ,\, \varphi (Y)\geq 2}{{\varphi (Y)}\choose{j}}$$ $$=\sum _{|Y|=h+1,\, \varphi (Y)\geq 2}\, \, \sum _{j\geq 2}(-1)^{j}{{\varphi (Y)}\choose{j}}=
\sum _{|Y|=h+1,\, \varphi (Y)\geq 2}(\varphi (Y)-1).$$

Since $a_{n-h}=0$ it follows that no such $Y$ can exist, or equivalently, for any two distinct edges $E,F$ we have $|E\cup F|\geq h+2$. If $Y\subset V(H), |Y|=h+2$ and $E,F\in E(H),E\neq F$ and $E,F\subset Y$ we get $E\cup F=Y$ since $|E\cup F|\geq h+2$. Since $a_{n-h-1}=0$ we deduce in the same way that $|E\cup F|\geq h+3$ and by induction we obtain that for any two distinct edges $E,F\in E(H)$ we have $|E\cup F|\geq 2h-r$, or $|E\cap F|\leq r$.\\ Let now $Y\subset V(H), |Y|=2h-r$ be a major component of a spanning subhypergraph of $H$ such that $Y$ contains exactly $j\geq 2$ edges. We shall prove that $j=2$. For this let $E,F\subset Y$ be two distinct edges such that $E\cup F=Y$. Suppose that there exists an edge $G,G\neq E,F$ such that $G\subset Y$. By denoting $a=|(E\backslash F)\cap G|$ and $b=|(F\backslash E)\cap G|$ we get $a+b\leq h$. Since $|G\cup E|=h+b\geq 2h-r$, $|G\cup F|=h+a\geq 2h-r$, it follows $a,b\geq h-r$, hence $a+b\geq 2h-2r$, which implies $h\geq 2h-2r$. But this contradicts the hypotheses $h\geq 3r-1$ and $r\geq 2$. For hypergraph $H$ we can write $$\sum _{|Y|=2h-r,\, \varphi (Y)=2}1 =
a_{n-2h+r+1}=m-1,$$ which implies that $H$ contains exactly $m-1$ pairs of edges $\{E,F\}$ such that $|E\cap F|=r$, or $|E\cup F|=2h-r$.\\
Let $p$ be such that $n-2h+2<p<n-2h+r+1$. If $Y\subset V(H),|Y|=n+1-p$ is a vertex subset inducing a major component of a spanning subhypergraph of $H$ it follows that $2h-r<|Y|<2h-1$.
For every three distinct edges $E,F,G$ of $H$ we have $$|E\cup F\cup G|\geq |E|+|F|+|G|-|E\cap F|-|E\cap G|-|F\cap G|\geq 3h-3r,$$ since every two edges have at most $r$ elements in common. But $3h-3r\geq 2h-1$ since $h\geq 3r-1$, which contradicts the property $|Y|<2h-1$. Hence one has $\varphi (Y)=2$. This yields $$\sum _{|Y|=n+1-p,\,  \varphi (Y)=2}1 =a_p=0.$$
It follows that no such $Y$ can exist, or for any two distinct edges $E,F$ we cannot have $2h-r<|E\cup F|<2h-1$, or $1<|E\cap F|<r$. But $H$ is antilinear, hence $|E\cap F|\neq 1$ and we have seen that $|E\cap F|\leq r$. It follows that $|E\cap F|=0$ or $r$, i.e., $H$ is also quasi-linear.\\
Since $H$ has $m$ edges, is quasi-linear and connected, it may be obtained from $P_{2}^{h,r}$ by succesively adding $m-2$ distinct edges such that every new edge has $r$ vertices in common with at least one existing edge. \\We will define two potential functions, $\alpha $ and $\beta$, for any $h$-uniform hypergraph $K$ of size $m$: $\alpha (K)=\alpha _{1}(K)-m$ and $\beta (K)=\alpha _{3}(K)-m$, where $\alpha _{1}(K)$ and $\alpha _{3}(K)$ are the numbers of induced subhypergraphs of $K$ isomorphic to $P_{2}^{h,r}$ and to $P_{3}^{h,r}$, respectively. We have deduced that for every $m\geq 1$ $\alpha (P_{m}^{h,r})=\alpha (H)=-1$. If $K$ is an $h$-uniform quasi-linear hypergraph, then by adding a new edge $E\subset V(K)$, $E\notin E(K)$ which intersects at least an edge from $E(K)$, we get a new hypergraph $K_1$ and $\alpha (K_1)\geq \alpha (K)$. Equality holds if and only if $E$ intersects exactly one edge from $E(K)$.
Since $\alpha (H)=\alpha (P_{2}^{h,r})=-1$, it follows that $H$ is obtained from $P_{2}^{h,r}$ by adding $m-2$ distinct edges such that every new edge has $r$ vertices in common with exactly one existing edge. This implies that every subhypergraph of $H$ induced by three edges has one of types a), b) or c). Since $P(H,\lambda )=P(P_{m}^{h,r},\lambda )$, by Lemma 2.1 we obtain that $\alpha _{3}(H)=m-2=\alpha _{3}(P_{m}^{h,r})$, hence $\beta (H)= \beta (P_{m}^{h,r})=-2$. With the same notation as above we deduce $\beta (K_1)\geq \beta (K)$ and equality holds if and only if $E$ intersects exactly one edge which belongs to exactly one path $P_{2}^{h,r}$, which is an induced subhypergraph of $K$, unless $K_1$ is a sunflower hypergraph.\\
Now the proof follows by induction: if we add a new edge to $P_{2}^{h,r}$ (having $\alpha (P_{2}^{h,r})=-1$) such that potential function $\alpha$ remains unchanged, we get $P_{3}^{h,r}$. Let $i\geq 3$; if we add a new edge to $P_{i}^{h,r}$ such that both potential functions $\alpha $ and $\beta $ remain unchanged, this new edge must have $r$ vertices in common only with a terminal edge of $P_{i}^{h,r}$ and one obtains in this way the hypergraph $P_{i+1}^{h,r}$.\\
II. In the case of cycles $C_{m}^{h,r}$ with $m\geq 4$ we deduce as above that polynomial $P(C_{m}^{h,r},\lambda )$ has $\alpha _{1}=m,\alpha _{2}={{m}\choose {2}}-m, \alpha _{3}=m$. If $H$ is antilinear and chromatically equivalent to $C_{m}^{h,r}$ then $H$ has order $m(h-r)$ and size $m$ and it is connected. As in the case of paths $P_{m}^{h,r}$ we deduce that $H$ has exactly $m$ unordered pairs of edges $\{E,F\}$ such that $|E\cap F|=r$ and $H$ is quasi-linear too. Also $H$ may be built from $P_{2}^{h,r}$ in $m-2$ steps, each step consisting in addition of a new edge $E$, having $r$ vertices in common with $t\geq 1$ existing edges $F_1,\ldots ,F_t$, i. e., $|E\cap F_1|=\ldots =|E\cap F_t|=r$.\\
We have $\alpha (C_{m}^{h,r})=\alpha (H)=0$, but $\alpha (P_{2}^{h,r})=-1$.
Since at each step potential function $\alpha $ increases or remains constant, it follows that in one step $\alpha $ increases by 1 and in $m-3$ steps it remains constant (equal to 0 or $-1$). It increases by 1 when the new edge $E$ intersects exactly two existing edges and remains constant when $E$ intersects exactly one existing edge. Suppose that $E$ intersects exactly two existing edges, $F_1$ and $F_2$, i. e., $|E\cap F_1|=|E\cap F_2|=r$ and
$|F_1\cap F_2|=r$. We shall prove that this case is not possible, i. e., we must have $F_1\cap F_2=\emptyset$. Suppose that $|F_1\cap F_2|=r$ and denote $i=|E\cap F_1 \cap F_2|$. It follows that $0\leq i\leq r$, $|E\cap (F_1\backslash F_2)|=|E\cap (F_2\backslash F_1)|=r-i$. In this case $E$ contributes $h-2r+i=|E\backslash (F_1\cup F_2)|$ new vertices. Since $P_{2}^{h,r}$ and $H$ have $2h-r$ and $m(h-r)$ vertices respectively, and whenever $\alpha $ remains unchanged the new edge contributes $h-r$ new vertices ($m-3$ times), we obtain that $i=0$, which means that $E,F_1,F_2$ induce a subhypergraph isomorphic to $C_{3}^{h,r}$.\\
In this case $H$ has the property that all subhypergraphs induced by 3 edges have the types a), b), c) and exactly one subhypergraph is isomorphic to $C_{3}^{h,r}$. A result similar to Lemma 2.1 also holds and the contribution of the spanning subhypergraph of $H$ consisting of $C_{3}^{h,r}$ and $n-3h+3r$ isolated vertices is $-\lambda ^{n-3h+3r+1}$, which must be added to the polynomial given by (4). We have $n-3h+3r+1>n-3h+2r+1$ and $n-3h+3r+1< n-2h+2$, unless $h=3r-1$. If $n-3h+3r+1<n-2h+2$ the monomial $-\lambda ^{n-3h+3r+1}$ does not appear in $P(C_{m}^{h,r},\lambda )$; if $h=3r-1$ the coefficient of $\lambda ^{n-2h+2}$ equals $\alpha _{2}-1= {{m}\choose{2}}-m-1$, a contradiction.\\
Consequently, $E$ intersects two existing edges $F_1,F_2$ such that $F_1\cap F_2=\emptyset $, which implies that $H$ contains an induced subhypergraph $H_1$ which is isomorphic to a cycle  $C_{s}^{h,r}$ with $4\leq s\leq m$. If $s=m$ then $H$ is isomorphic to $C_{m}^{h,r}$ and we are done. Otherwise, $H$ may be obtained from $C_{s}^{h,r}$ by succesively adding $m-s$ distinct edges such that every new edge has $r$ vertices in common with exactly one existing edge. We have $\beta (C_{s}^{h,r})=0$; at the first step we get $\beta (C_{s}^{h,r}+E)=1$ if $E$ is such an edge. Since $\beta $ is increasing, we deduce $\beta (H)\geq 1$. But in this case every 3 edges of $H$ induce a subhypergraph of type a), b) or c), which implies that $\beta (H)=\beta _{3}-m=\alpha _{3}-m=0$, a contradiction.

\end{proof}
Note that $P_{m}^{h,r}$ is not chromatically unique for any $m\geq 3,r\geq 1$ and $h\geq 2r+1$, since any hypergraph containing a pendant path of length at least two is not chromatically unique [14].\\
Since every quasi-linear hypergraph is antilinear for every $r\geq 2$ we get:
\begin{corollary}
Let $r\geq 2,h\geq 3r-1,m\geq 3$ and $H$ be a quasi-linear hypergraph such that $P(H,\lambda )=P(G,\lambda )$, where $G$ is $P_{m}^{h,r}$ or $C_{m}^{h,r}$. Then $H$ is isomorphic to $G$.
\end{corollary}

\subsection*{Acknowledgements}
The author thanks the referee for helpful comments.

\begin{thebibliography}{999}
\bibitem{berge}
C.~Berge.  \newblock {\em Graphs and hypergraphs}. \newblock North-Holland, Amsterdam, 1973.
\bibitem{bok}
S.~A. Bokhary, I.~Tomescu, and A.~A. Bhatti. \newblock On the chromaticity of multi-bridge hypergraphs. \newblock {\em Graphs Combin.}, 25(2):145--152, 2009.
\bibitem{bor-laz}
M.~Borowiecki and E.~{\L}azuka. \newblock Chromatic polynomials of hypergraphs. \newblock {\em
Discuss. Math., Graph Theory}, 20:293--301, 2000.
\bibitem{ch-whi}
C.~Y. Chao and E.~G. Whitehead, Jr.. \newblock On chromatic equivalence of graphs. \newblock In
{\em "Theory and Applications of Graphs"} (Y. Alavi and D. R. Lick, Eds.), volume 642 of
{\em Lecture Notes in Math.}, pages 121--131. Springer, New York/
Berlin, 1978.
\bibitem{del}
D.~Dellamonica, V.~Koubek, D.~M. Martin, and V.~R{\" o}dl. \newblock On a conjecture of Thomassen concerning subgraphs of large girth. \newblock {\em J. Graph Theory}, 67:316--331, 2011.
\bibitem{doh}
K.~Dohmen. \newblock {\em Chromatische Polynome von Graphen und Hypergraphen}. \newblock Dissertation, D{\" u}sseldorf, 1993.
\bibitem{erdos}
P.~Erd{\" o}s and R.~Rado. \newblock Intersection theorems for systems of sets. \newblock {\em J. London Math. Soc.}, 35:85--90, 1960.
\bibitem{fur}
Z.~F{\" u}redi. \newblock On finite set-systems whose intersection is a kernel of a star.
\newblock {\em Discrete Math.}, 47(1):129--132, 1983.
\bibitem{kohteo}
K.~M. Koh and K.~L. Teo. \newblock The search for chromatically unique graphs. \newblock {\em Graphs Combin.}, 6:259--285, 1990.
\bibitem{tom}
I.~Tomescu. \newblock Chromatic coefficients of linear uniform hypergraphs. \newblock {\em J. Combinatorial Theory Ser. B}, 2(72):229--235, 1998.
\bibitem {tom1}
I.~Tomescu. \newblock Sunflower hypergraphs are chromatically unique. \newblock {\em Discrete Math.}, 285:355--357, 2004.
\bibitem{tom2}
I.~Tomescu. \newblock On the chromaticity of sunflower hypergraphs $SH(n,p,h$). \newblock {\em Discrete Math.}, 307:781--786, 2007.
\bibitem{tom3}
I.~Tomescu and S.~Javed. \newblock On the chromaticity of quasi-linear hypergraphs (submitted).
\bibitem{tom4}
I.~Tomescu. \newblock On chromaticity of hypergraphs with pendant paths (submitted).
\bibitem{wal}
M.~Walter. \newblock Some results on chromatic polynomials of hypergraphs. \newblock {\em Electronic J. Combinatorics}, 16, R94, 2009.

\end{thebibliography}

\end{document}
