Some results on chromaticity of quasi-linear paths and cycles

Ioan Tomescu¹

¹Faculty of Mathematics and Computer Science, Bucharest University, Romania and Abdus Salam School of Mathematical Sciences, GC University, Lahore, Pakistan

The electronic journal of combinatorics, Tome 19 (2012) no. 2

Résumé

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

Détail

DOI : 10.37236/2370

Classification : 05C15, 05C65, 05C38
Mots-clés : quasi-linear hypergraph, sunflower hypergraph, quasi-linear path, quasi-linear cycle, chromatic polynomial, chromatic uniqueness, potential function