3 problems

The Implicit Graph Conjecture
arXiv@arxiv
Implicit Graph Conjecture. Every such class ${\mathcal F}$ admits an adjacency labeling scheme with labels of size $O(\log n)$ .
Conjecturerefutedgraph-labeling graph-sketching hereditary-graph-classes
1
The stable hereditary-class adjacency sketch conjecture
arXiv@arxiv
Stable hereditary-class adjacency sketch conjecture. The class ${\mathcal F}$ admits a constant-size adjacency sketch.
Conjecturerefutedgraph-sketching hereditary-graph-classes stable-graphs
0
The strong Erdős–Hajnal conjecture for adjacency sketchable graph classes
arXiv@arxiv
Strong Erdős–Hajnal conjecture for adjacency sketchable classes. All adjacency sketchable graph classes have the strong Erdős–Hajnal property.
Conjecturerefutedcommunication-complexity erdos-hajnal-property graph-sketching
0

The Implicit Graph Conjecture