44 problems

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$, an edge coloring assigns colors to edges so that incident edges receive different colors. Let $\chi'(G)$ be the chromatic index and $\chi'_\ell(G)$ the list chroma…

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

Vizing's conjecture. Every equivalence class of $k$-colorings of a line graph contains a minimum coloring, for every choice of $k$.

Georgakopoulos's conjecture. The line graph of every 4-edge-connected graph has a Hamiltonian circle.

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, and let $L(G)$ denote its line graph. Write $n^{+}(L(G))$ and $n^{-}(L(G))$ for the numbers of positive and negative adjacency eigenvalues of…

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 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's equivalence. Thomassen's conjecture is equivalent to Matthews–Sumner's conjecture.

Let $G$ be a loopless multigraph, and let $L(G)$ denote its line graph. A graph is chromatic-choosable when its chromatic number equals its list chromatic number, namely, when…

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$.

Hriňáková–Knor–Škrekovski conjecture. For sufficiently large order $n$, the path $P_n$ has the smallest value of $R_2$ among all trees on $n$ vertices.

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)$ denote its line graph. The choice number of a graph is the least integer $k$ such that every assignment of lists of $k$ colors to its vertices ad…

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…

Let $G$ be a finite, simple, undirected essentially $4$-edge-connected graph, and let $L(G)$ denote its line graph. A graph is Hamiltonian if it contains a cycle through all its ve…