22 problems

APUD(1,1) recognition conjecture. Given a graph $G$, it can be determined whether $G\in\mathrm{APUD}(1,1)$ in polynomial time.

Let $D$ be a chord diagram, and let its intersection graph $\Gamma(D)$ be the simple graph whose vertices are the chords of $D$, with two vertices adjacent exactly when the corresp…

Lokshtanov–McCarty's conjecture. There exists a graph $H'$ such that every $H$-induced-minor-free graph with maximum degree at most $\Delta$ is a region intersection graph over an…

The above-threshold product-structure conjecture. For every $\alpha \geq s(n)$, the class of intersection graphs of $\alpha$-free homothetic regular $n$-gons has product structure.

The no-product-structure conjecture. For every $\alpha < s(n)$, the class of intersection graphs of $\alpha$-free homothetic regular $n$-gons does not have product structure.

The canonical-drawing characterization. The class of intersection graphs of $\alpha$-free homothetic regular $n$-gons admits product structure if and only if their canonical drawin…

A graph class $\mathcal{F}$ is proper if some graph is not isomorphic to any graph in $\mathcal{F}$. Write $\int(\mathcal{F})$ for the class of intersection graphs of collections of…

For $\alpha>0$, an intersection graph of $n$ boxes in $\mathbb{R}^3$ has one vertex for each box and edges joining intersecting boxes; it is triangle-free when it has no $3$-cycle,…

An intersection graph of lines in $\mathbb{PR}^3$ has one vertex for each projective line and edges joining intersecting lines; it is triangle-free when it has no $3$-cycle. Polyno…

Let $g\in\mathbb{N}$. An intersection graph of lines in $\mathbb{R}^3$ has one vertex for each line and edges joining intersecting lines; its girth is the length of its shortest cy…

APUD recognition conjecture. Recognition of $\mathrm{APUD}(k,m)$ is NP-complete.

A grounded segment graph is the intersection graph of a collection of line segments grounded on a common line. Grounded segment-graph conjecture. The class of grounded segment grap…

Generalized weak-subdivision conjecture. For every $\epsilon>0$ and integer $t\geq 3$, there exists $\delta>0$ such that, if $G$ has at most

Bipartite curve-family conjecture. For every $k$ there is a constant $c_k>0$ such that there are subfamilies $\mathcal{A}_0\subseteq\mathcal{A}$ and…

Asymptotic cardinality conjecture. The maximum cardinality of a $k$-system of simple loops on $S_g$ is

Containment conjecture. The class of interval filament graphs is properly contained in the class of co-strongly pseudo transitive graphs of the first type.

Let $K_n$ be a complete geometric graph on $n$ points in general position in the plane. A family of subgraphs is $K_3$-intersecting if every two members intersect in a triangle. Qu…

Let $Y$ be a fixed graph, and let $\mathcal{G}(Y)$ be the class of intersection graphs of connected subgraphs of subdivisions of $Y$. Non-universality conjecture. For every fixed g…

Bounded-intersection hub curve conjecture. For every $t$, the intersection graph of $\mathcal{F}$ is $\chi$-bounded.

Large-order extremal construction conjecture. For any $n\geq 2\times2^{d/2}+(r-2)$, the maximum number of edges in a $K_{r+1}$-free graph in $\mathcal{I}(n,d)$ is attained by a gra…

Small-order extremal conjecture. For any $n\leq 2\times2^{d/2}+(r-2)$, the maximum number of edges in a $K_{r+1}$-free graph in $\mathcal{I}(n,d)$ is attained by a graph $G$ which…

Connectivity threshold conjecture.