Chain Graphs have Unbounded Readability

Abstract: A triangle-free graph

G

is called read-

k

when there exists a monotone Boolean formula

p h i

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

p h i

. The smallest such

k

is called the readability of

G

. We exhibit a very simple class of bipartite chain graphs on

2 n

vertices with readability

O m e g a (s q r t f r a c l o g n l o g l o g n)

.

This page was built for publication: Chain Graphs have Unbounded Readability