Some Results on Chromaticity of Quasi-Linear Paths and Cycles

Ioan Tomescu

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$.

 


Keywords


Quasi-linear hypergraph; Sunflower hypergraph; Quasi-linear path; Quasi-linear cycle; Chromatic polynomial; Chromatic uniqueness; Potential function

Full Text: PDF