21 problems

Chordal graph representation conjecture. Let $H$ be a chordal graph. There are chordal graphs $G$ and $G'$ such that $H$ is isomorphic to both $C(G)$ and $C_R(G')$.

The maximal chordal subgraph conjecture. Then

Let $G$ be a finite graph, and call it $r$-locally chordal if every ball of radius $r$ in $G$ is chordal. Let $|V(G)|$ denote the number of vertices of $G$ and let…

Bounded-mad backbone colouring conjecture.

Backbone colouring conjecture.

Let $G$ be a chordal graph, let $I(G)$ be its edge ideal, let $I(G)^{[k]}$ denote its $k$-th square-free power, let $\nu(G)$ be its matching number, and let $\mathrm{aim}(G,k)$ be…

Let $G$ be a connected chordal graph admitting a tree representation $T$, where $T$ is a subdivided caterpillar. Subdivided-caterpillar Gallai conjecture. Then … This asserts that…

Let $G$ be an undirected graph, and let $P_G$ denote the spanning tree generating function corresponding to $G$. A polynomial is homaloidal if its polar map is birational. Chordali…

For an integer $k\geq 1$, a $k$-forest is a $K_{k+2}$-free chordal graph; in particular, a $2$-forest is a $K_4$-free chordal graph. An even-hole-free graph has no induced cycle of…

Let $t\geq 4$ be an integer, let $H$ be a graph, and call $H$ $K_4$-free chordal if it is chordal and contains no induced subgraph isomorphic to $K_4$. An even-hole-free graph has…

Figueiredo et al.'s conjecture. $G$ is Class 2 if and only if it is subgraph-overfull. This conjecture proposes a characterization of edge-chromatic Class 2 chordal graphs by the s…

Reduced clique graph recognition conjecture. There is a polynomial-time algorithm for deciding whether a given graph is isomorphic to $C_R(G)$ for some chordal graph $G$.

Seven-hole conjecture. There is no chordal graph $G$ such that $C_R(G)$ contains an induced cycle with seven or more vertices.

Herzog–Hibi–Ohsugi conjecture. If $G$ is chordal, then

Assume the higher d-separation conjecture: whenever two vertices of a DAG have minimum d-separating-set size at least $2$, the vanishing ideal is not toric. Let $G$ be a chordal di…

Chordal graph k-path vertex cover conjecture.

Hendry's conjecture. Every Hamiltonian chordal graph is fully cycle extendible.

Let $G$ be a 3-clique graph, and let Hilton's condition mean the condition for a simple graph with an even number of vertices and a universal vertex that … where…

Optimal-size clique transversal conjecture. Every $4$-chordal graph with $n$ vertices has a clique transversal of size at most $2n/7$.

Erdős–Gould–Yuster–Oz conjecture. Any graph with $n$ vertices and more than $n^2/3$ edges contains a chordal subgraph with at least $8n/3-4$ edges. The complete tripartite graph wi…

Forbidden-subgraph conjecture. A $6$-chordal graph is $\frac{1}{2}$-hyperbolic if and only if it does not contain any of the ten special graphs $G_1,G_2,G_3,C_4,C_6,H_i$,…