79 problems

Let $G$ be a connected simple graph of order $n$, with adjacency eigenvalues $\lambda_1,\ldots,\lambda_n$. Define $s^{+}(G)=\sum_{\lambda_i>0}\lambda_i^2$ and…

Let $(G,\sigma)$ be a signed planar graph, and let $g_{ij}(G,\sigma)$ denote the corresponding signed girth parameter; let $SPC(k)$ be the signed projective cube of dimension $k$,…

All graphs are finite, simple, undirected graphs. Let $G$ be a graph and let $\sigma:E(G)\to\{-1,+1\}$ be a signature; the pair $(G,\sigma)$ is a signed graph, with underlying grap…

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)$…

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

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,\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…

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 a finite set of signed graphs be a GS set when its forbidden induced-subgraph class has bounded balanced chromatic number, and call it minimal if no proper subset is a GS set.…

Let $(K_3,-)$ denote the signed triangle with the specified signature, let $(K_4,M)$ denote the signed complete graph whose negative edges form a matching of size two, and let…

For a signed graph $\widehat{G}$ and a vertex $u$, let $N[u]$ denote the closed neighborhood of $u$, and let $\chi_b$ denote balanced chromatic number. Bounded-neighborhood conject…

Let $F$ be a linear forest, meaning a forest whose connected components are paths. Let $\widehat{(K_4,-)}$ be the specified signed complete graph, and call a finite set of signed g…

Let $\widehat{K}_2^- = \widehat{(K_2,-)}$ and let $\widetilde{G}$ denote the signed graph obtained from a graph $G$ by replacing each edge with a digon. A finite set of signed grap…

Let $n_s(\lambda,p)$ be the minimum number of vertices of a signed graph with balanced chromatic number at least $p$ and negative girth at least $\lambda$. Signed-graph extremal co…

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 $\lambda>0$ and $p\in\mathbb{N}^+$. For a finite family $\mathcal{F}$ of signed graphs, let $M_{p,\mathcal{F}}(\lambda,N)$ be the maximum of $\operatorname{mult}(-\lambda,G)$ o…

Let $G$ be a signed subcubic graph, meaning a graph of maximum degree at most $3$ whose edges have signs. Let $(K_4,-)$ denote the negatively signed complete graph on four vertices…

Let $G$ be a graph of order $n \geq 1$, let $\sigma$ be a signing of $G$, and let $\ell(G,\sigma)$ denote the frustration index. Let $C_r(G,\sigma)$ denote the relaxed confusion nu…

Let $(G,\sigma)$ be a signed graph on $n$ vertices. The confusion-number upper-bound conjecture. … This conjecture proposes a general upper bound for the confusion number of a sign…

Let $\Sigma_1$ and $\Sigma_2$ be signed complete graphs. Write $\Sigma_1\cong\Sigma_2$ when they are isomorphic, and let $\mathscr B(\Sigma,x,y)$ and $\mathsf E(\Sigma,x,y)$ denote…

For each integer $n\geqslant 0$ and each vector $\bm{a}\in\{-1,0,1\}^n$, let $\mathcal{T}_{\bm{a}}$ be the associated signed threshold graph, with bivariate chromatic polynomial…