44 problems

Let $\mathcal{F}$ be a finite family of axis-parallel rectangles. Write $\tau$ for the minimum number of points meeting every member of $\mathcal{F}$, and $\nu$ for the maximum num…

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…

Let $n\geq 2$ be a positive integer, and let $\mathcal{F}$ be the class of intersection graphs of families of spheres in $\mathbb{R}^n$. The asymptotic dimension of a graph class i…

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…

Even-chromaticity conjecture. If

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…

A $k$-DIR graph is an intersection graph of line segments in the plane whose segments lie in at most $k$ directions. A planar graph is a graph that can be embedded in the plane wit…

Single-crossing polygonal 2-chain conjecture. The class of disjointness graphs of single-crossing polygonal $2$-chains is $\chi$-bounded.

Let $\mathcal{F}$ be a family of $n$ axis-parallel boxes in the plane or in $\mathbf{R}^d$ for $d>2$, and let $G=G(\mathcal{F})$ be its intersection graph. If the maximum number of…

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

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

B$_k$-EPG recognition conjecture. Determining the least $k$ such that an arbitrary graph is B$_k$-EPG is NP-complete for general $k$.

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…

3-bend conjecture. The bound of three bends is tight for 3-thin graphs: there exists a 3-thin graph that has no $B_2$-VPG representation.

Burling-graphs obstruction conjecture. Burling graphs might be the only obstruction to intersection graphs of segments in the plane being $c7$-bounded.

For a positive integer $k$, let $B_k$ denote the class of edge intersection graphs of paths on a grid in which each path has at most $k$ bends, and let $B_k^m$ denote the subclass…

For a positive integer $k$, let $B_k$ denote the class of edge intersection graphs of paths on a grid in which each path has at most $k$ bends, and let $B_k^m$ denote the subclass…

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

Pach–Tomon conjecture. Their result for string graphs represented by x-monotone curves should remain valid without the assumption that the curves are x-monotone.