Some Results on Chromaticity of Quasi-Linear Paths and Cycles

  • Ioan Tomescu
Keywords: Quasi-linear hypergraph, Sunflower hypergraph, Quasi-linear path, Quasi-linear cycle, Chromatic polynomial, Chromatic uniqueness, Potential function


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


Article Number