Abstract

In this paper, all graphs and hypergraphs are finite. For any ordered hypergraph $H$, the associated graph $G_H$ of $H$ is defined. Some basic graph-theoretic properties of $H$ and $G_H$ are compared and studied in general and specially via the largest negative real root of the clique polynomial of $G_H$. It is also shown that any hypergraph $H$ contains an ordered subhypergraph whose associated graph reflects some graph-theoretic properties of $H$. Finally, we define the depth of a hypergraph $H$ and introduce a constructive algorithm for coloring of $H$.

Keywords: Hypergraph, Clique polynomial, Interval cycle.

MSC: 05C65, 05C99

Pages:  9$-$13     

Volume  59 ,  Issue  1$-$2 ,  2007