Chain Graphs have Unbounded Readability
| dc.creator | Golumbic, Martin Charles | |
| dc.creator | Peled, Uri N. | |
| dc.creator | Rotics, Udi | |
| dc.date | 2006-10-15 | |
| dc.date.accessioned | 2026-07-07T07:29:05Z | |
| dc.date.available | 2026-07-07T07:29:05Z | |
| dc.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}})$. | |
| dc.description | 17 pages, 2 figures, LaTeX2e, uses amsmath and pstricks | |
| dc.identifier | https://arxiv.org/abs/math/0610456 | |
| dc.identifier | http://arxiv.org/abs/math/0610456 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/117968 | |
| dc.subject | Combinatorics | |
| dc.subject | 68R05 (Primary), 94C10, 05C99 (Secondary) | |
| dc.title | Chain Graphs have Unbounded Readability | |
| dc.type | text |