Chain Graphs have Unbounded Readability

Details Chain Graphs have Unbounded Readability Chain Graphs have Unbounded Readability

2006-10-15

arxiv.org/abs/math/0610456v1

Mathematics

Combinatorics

17 pages, 2 figures, LaTeX2e, uses amsmath and pstricks

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Chain Graphs have Unbounded Readability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Chain Graphs have Unbounded Readability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Chain Graphs have Unbounded Readability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-477069