3,531 problems

Let $G=(X,E)$ be a locally finite Borel graph on a standard Borel space $X$. Does there always exist a Borel coloring $c:X\to\{0,1\}$ such that, for every $x\in X$, the number of n…

For every connected graph $G$ with $n=|V(G)|$ vertices, the edges of $G$ admit a decomposition into at most $\left\lceil\frac{n}{2}\right\rceil$ paths.

For a finite tree $T$ with vertex degrees $d(v)$, define its Euler Sombor index by $EUS(T)=\sum_{uv\in E(T)}\sqrt{d(u)^2+d(v)^2+d(u)d(v)}$. For trees with a prescribed diameter $d$…

All graphs under consideration are finite and simple. For a graph $G$ and a vertex $v$, let $d_G(v)$ denote the degree of $v$. Dean's conjecture. For every integer $k \ge 3$, every…

Tree equidistant dimension conjecture.

Chemical antiregular graph conjecture. The same graphs as in Theorem $$ have maximum value of $\sigma_t^{f(n)}$ even if $f(n)$ is a constant in the interval $(0,1)$.

Sign conjecture. For any tree on $n$ vertices,

Conjecture on ternary strong nodal domains. For any eigenfunction $f$ of $H(n,3)$, $n\geq 1$, with eigenvalue $3n$ we have $\mathrm{SND}(f)\geq n+1$.

Let $G_n$ be the graph associated with $S(0,n)$, and let $K_{\ell,v,n}$ denote the number of paths of length $\ell$ in $G_n$ that start at a vertex labeled $v$ and end at a vertex…

For each integer $n\ge 3$, let $\vec K_n$ denote the complete directed graph on $n$ vertices, and let $\genfrac{\{} {\}}{0pt}1{\vec K_n}{n-2}$ denote the number of admissible parti…

Partition-graph de-anonymization conjecture. If a single user is de-anonymized by an optimizing attacker from $G$, the number of remaining perfect matchings is at most the number r…

Let $G$ be a decorated unicyclic graph with cycle length parameter $g$, let $R_G$ be its curvature operator, and let $w^\ast$ denote the Perron metric. Write … and let $\varphi$ be…

Let $(s_n)$ be an appropriate sequence of positive integers, and let $G_n$ be the action graph associated with $s_n$. For $n\geq 1$, write $z_n$ for the number of new vertices labe…

Let $\mathcal{G}$ be a graph on $n$ vertices with non-abelian automorphism group $G=\operatorname{Aut}(\mathcal{G})$ of order $n$, and let $\mathbf{x}$ be a single observation of a…

Let $G$ be a graph, and let $T\chi_G^o(q)$ denote its total oriented chromatic quasisymmetric function. Say that cycles of $G$ are edge-disjoint when no two cycles share an edge. S…

Planar-graph unimodality conjecture. For any planar graph $G$ of order $n$, the sequence $\{\st{G}{k}\}_{k=1}^n$ is unimodal. This property is known for paths, cycles, trees, lolli…

Almost-all-graphs unimodality conjecture. For almost all graphs $G$, the sequence $c^{\mathcal{P}}_i(G)$, $0\leq i\leq n(G)$, is unimodal.

Tree discriminant magnitude homology conjecture. For $k=3,4$,

Degree-bounded expected value polynomial conjecture. The polynomial $\mathcal{E}(G,S,q)$ has degree at most $\ell$ if and only if, for every $1\leq k\leq s$,

Let $J_n(x)$ be a linear Jaco graph of order $n\geq1$. A diam-path is a path of diameter length, and let $P_d$ be a primary minimal dom-path, meaning a minimal path from $v_1$ to…

Let $J_n(x)$ be the finite linear Jaco graph of order $n$, and let $\Delta(J_n(x))$ denote its maximum degree. A sequence is $p$-graphical for a graph family $\mathcal{F}$ when it…

Let $P_k$ and $P_m$ be paths on $k$ and $m$ vertices, respectively, and let $G=P_k\mathbin{\square}P_m$ denote their Cartesian product. For a graph $G$, write ${\mathbb D}(G)$ for…

Path-tree recurrence conjecture. For $0\leq k\leq n$ and all $\ell\geq 0$,

Let $\mathrm{Fw}_n$ denote the boundary framework, let $L_r(n)$ be the vertices of local simplex dimension $r$, and let $(n)$ and $(1^n)$ be the two antenna vertices. Low-dimension…

Let $G_n$ be the partition graph, let $K_n$ be its clique complex, let $L_r(n)$ denote the vertices of local simplex dimension $r$, let $\Delta(n)$ be the maximal local simplex dim…