Chain Graphs have Unbounded Readability

Golumbic, Martin Charles; Peled, Uri N.; Rotics, Udi

Chain Graphs have Unbounded Readability

Authors

Golumbic, Martin Charles

Peled, Uri N.

Rotics, Udi

Description

A triangle-free graph $G$ is called read-$k$ when there exists a monotone Boolean formula $ϕ$ whose variables are the vertices of $G$ and whose minterms are precisely the edges of $G$, such that no variable occurs more than $k$ times in $ϕ$. The smallest such $k$ is called the readability of $G$. We exhibit a very simple class of bipartite chain graphs on $2n$ vertices with readability $Ω(\sqrt{\frac{\log n}{\log \log n}})$.
17 pages, 2 figures, LaTeX2e, uses amsmath and pstricks