34 problems

Graham's tree reconstruction conjecture. For each sequence of natural numbers $a_0,a_1,a_2,\ldots$, all the conditions $|L^{(j)}(G)|=a_j$ for $j\geq 0$ are satisfied by at most one…

Let $G$ be a graph, and let $\sigma(G)$ denote the minimum number of equivalence relations needed to cover the line graph structure under the paper's definition. For an integer…

Let $G$ be a graph. Its choice number $ch(G)$ is the least integer $k$ such that every assignment of a $k$-element list of colors to each vertex admits a proper coloring from the a…

Let $G$ be a finite simple graph. For a non-empty subgraph $H$ of $G$, define its Ore-degree in $G$ by … with $\sigma_G(H)=0$ when $H$ is empty. Suppose that $H$ is a bipartite sub…

For a finite simple graph $G$, let $L(G)$ denote its line graph, let $G^2$ denote the graph in which two vertices are adjacent exactly when they are at distance at most two in $G$,…

For a graph $G$, its line graph $L(G)$ has one vertex for each edge of $G$, with two vertices adjacent exactly when the corresponding edges share an endpoint. Let $\chi$ and…

Ryjáček et al.'s conjecture. Every $4$-connected line graph with minimum degree at least $5$ is Hamiltonian.

Let $G$ be a connected graph, and let $L(G)$ denote its line graph. Let $n^+(L(G))$ and $n^-(L(G))$ be the numbers of positive and negative eigenvalues of the adjacency matrix of…

Hriňáková–Knor–Škrekovski conjecture. For large $n$ and $k\geq 2$, among all graphs $G$ on $n$ vertices, $R_k(G)$ attains its maximum at $G=K_n$ and its minimum at $G=P_n$.

Let $G$ be a 2-edge-connected simple cubic graph with an even number of edges. Its line graph $L(G)$ has one vertex for each edge of $G$, with two vertices adjacent when the corres…

Let $G$ be a graph and let $L(G)$ be its line graph, whose vertices are the edges of $G$, with two vertices adjacent when the corresponding edges share an endpoint. Write $\chi$ fo…

Hypergraph line-graph connectivity conjecture. For any $r\geq 2$, there is an integer $\phi(r)$ such that every $\phi(r)$-connected line graph of a rank $r$ hypergraph is Hamiltoni…

Let $G$ be a graph, let $L(G)$ denote its line graph, and let $\Delta(G)$ denote its maximum degree. An orientation is semi-transitive when it is acyclic and has no shortcuts. Plan…

Let $G$ be a graph, let $L(G)$ denote its line graph, and let $\Delta(G)$ denote its maximum degree. A graph is word-representable if it admits a word representation, and an orient…

Unique minimal subgraph conjecture. If $G\in\Lambda_n$ and $G$ is not the disconnected union of two graphs in $\Lambda_n$, then there exists a unique graph $G'\in\lambda_n$ such th…

Unicyclic-components conjecture. If $G\in\lambda_n$, then $G$ has unicyclic components.

Non-isomorphic subgraph conjecture. If $G_1\not\cong G_2$ and $G_1,G_2\in\Lambda_n$, then $G$ has a sequence that diverges by order.

Divergence characterization conjecture. The graph $G$ has a sequence that diverges by order if and only if there exists a $k$ such that $HL^k(G)$ has a connected subgraph $G'$ wher…

Line-graph conjecture. If a spider $S$ is $e$-positive, then its line graph $S_L$ is $e$-positive.

Let $G$ be a connected graph with at least $k$ vertices and at least $k$ edges, and let $L(G)$ be its line graph. For a set $S\subseteq V(G)$ with $|S|\geq 2$, let $\lambda_G(S)$ b…

Let $f_G(n,m)$ denote the least number of independent $n$-sets in a graph $G$ that guarantees a rainbow independent set of size $m$. Exceptional-line-graph conjecture. If $G$ is th…

Let $K_n$ be the complete graph on $n$ vertices, let $L(K_n)$ be its line graph, and let $\chi”$ denote total chromatic number. Vignesh et al.'s conjecture. For every complete grap…

Let $s$ be an integer. An edge $\lambda$-choosable graph is a graph whose line graph is colourable from every list assignment whose list-size pattern is the partition $\lambda$. Th…

Let a graph $G$ be edge $k$-colourable if its line graph is $k$-colourable, and edge $k$-choosable if its line graph is $k$-choosable. The List Colouring Conjecture. Every edge $k$…

Mohar's conjecture. If $G$ is a $(\Delta(G)+1)$-edge-critical graph, then $L(G)$ is strong $(\Delta(G)+1)$-chromatic-choosable.