pith. sign in

arxiv: math/0610456 · v1 · submitted 2006-10-15 · 🧮 math.CO

Chain Graphs have Unbounded Readability

classification 🧮 math.CO
keywords readabilitycalledchaingraphsverticeswhosebipartiteboolean
0
0 comments X
read the original abstract

A triangle-free graph $G$ is called read-$k$ when there exists a monotone Boolean formula $\phi$ 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 $\phi$. 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 $\Omega(\sqrt{\frac{\log n}{\log \log n}})$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.