120 problems

A signed graph is flow-admissible if it admits a nowhere-zero flow. Bouchet's 6-flow conjecture. Every flow-admissible signed graph has a nowhere-zero 6-flow. This conjecture exten…

Let $G$ be a $d$-regular graph, let $A_\sigma$ be the signed adjacency matrix associated with a signing $\sigma$ of $G$, and write $\rho(A_\sigma)=\max_i|\lambda_i(A_\sigma)|$. Bil…

Signed-graph $K_5$-minor conjecture. Any signed graph $(G,\sigma)$ which has neither a $(K_5,-)$-minor nor induces an element of $\mathcal{O}_{k+1}$ maps to $SPC(k)$.

Let $(G,-)$ be the signed graph obtained from a graph $G$ by assigning a negative sign to every edge, and let $(K_t,-)$ be the all-negative signed complete graph. A signed graph mi…

Let $\Gamma$ be a signed complete graph with $n$ vertices and $k$ negative edges, where $k<n-1$. The negative edges are said to induce a star $K_{1,k}$ when they form the edge set…

A simple planar signed graph is a signed graph whose underlying graph is simple and planar, and a graph is 0-free 4-colourable if it admits a zero-free colouring with four colours.…

Let an Adinkra be a signed graph with signed Laplacian $L$, and let its invariant factors mean the diagonal entries in the Smith normal form of $L$. A signature is the choice of si…

Let $n$ be the number of vertices of a unicyclic graph, let $C_n$ denote the cycle on $n$ vertices, and let $P_n^6$ denote the unicyclic graph specified in the source. Caporossi et…

Let $K_n$ be the complete graph on $n$ vertices, let $\sigma$ be a signature on $K_n$, and let $\chi ' (K_n, \sigma)$ denote its signed chromatic index. Chromatic-index conjecture.…

Let $\widehat{\mathit{SS}}(n,k)$ be the signed Schrijver graph, and consider any signed graph switching-equivalent to it. The negative-edge-induced graph is the graph whose edges a…

Two-cliques edge-coloring conjecture. The signed edge-chromatic number satisfies

Let $(G,-)$ be a signed graph whose underlying graph is $G$, with every edge negative, and let $(K_{k+1},-)$ denote the complete graph on $k+1$ vertices with every edge negative. A…

Let $G$ be a nontrivial graph with maximum degree $\Delta>1$. A signed graph on $G$ is a pair $\Gamma=(G,\sigma)$, where $\sigma$ is a signature of $G$. Gregory's conjecture. There…

Let $S$ be a surface, let $n_S$ be the largest order of a complete graph that embeds into $S$, and let $\gamma(G,\sigma)$ and $\gamma^*(G,\sigma)$ denote the relevant orientable an…

Frustration equality conjecture. For every signed cubic graph $\Sigma$,

Let $C_n(1,2)$ be the circulant graph on even $n$ vertices, let $A_\sigma$ range over its signed adjacency matrices, and define … The switching classes are coordinatized by triangl…

Let $\Sigma$ be a signed graph. Denote by $p^-(\Sigma)$ the maximum number of edge-disjoint negative cycles, by $l(\Sigma)$ its frustration index, and by $p(\Sigma)$ the maximum nu…

Let $K_{n_1,n_2,\ldots,n_k}$ be a complete multipartite graph with $k\geq 3$. Let $-K_{n_1,n_2,\ldots,n_k}$ denote the signature in which every edge is negative, and write $l(-G)$…

Guo–Wang–Li conjecture. One has

Let $(G,\sigma)$ be a planar signed graph. A signed DP-coloring is a correspondence coloring for signed graphs, with admissible options assigned to vertices as in Jin, Kang, and St…

Let $(G,\sigma)$ be a signed planar graph, meaning that $G$ is a planar graph equipped with a signature $\sigma$. Its girth is the length of its shortest cycle. Girth-four signed c…

A signed graph $(G,\sigma)$ is a graph with a positive or negative sign on each edge. Its frustration index $l(G,\sigma)$ is the minimum number of negative edges among signatures s…

Let $\Gamma=(G,\sigma)$ be a connected signed graph of order $n$. Let the Laplacian eigenvalues of $\Gamma$ be ordered as … and let its vertex degrees be ordered as … Hou–Li–Pan co…

Let $(G,\sigma)$ be a signed connected simple subcubic graph, where $v(G)$ denotes the number of vertices of $G$, $F(G,\sigma)$ denotes its frustration index, and the girth is the…

The Guenin conjecture. The class of partial $3$-trees in the theorem stating that a signed partial $3$-tree $(G,\sigma)$ maps to $SPC(k)$ if and only if it has no element of…