23 problems

Let $K_{m,n}$ be a complete bipartite graph with independent vertex sets $\{a_1,\dots,a_m\}$ and $\{b_1,\dots,b_n\}$. Place $a_i$ at $(i,0)$ on the $x$-axis and $b_j$ at $(0,j)$ on…

Complete bipartite graph ideal degree conjecture. The graph ideal for $G=K_{m,n}$ is generated in degree at most

Let $K_{a,b}$ be a bidirectional complete bipartite graph with all edges of equal weight, where $a>b$. Let $A$ and $B$ be its partite sets, with $|A|=a$ and $|B|=b$. For vertices…

Let $K_{m,n}$ be the complete bipartite graph whose vertex set is partitioned into parts of sizes $m$ and $n$, with every vertex in one part adjacent to every vertex in the other.…

K{3,3} algebraic-connectivity conjecture. Based on computer experiments, the lower bound proved earlier in the paper is conjectured to be tight, namely

Let $K_{3,t}$ be the complete bipartite graph with parts of sizes $3$ and $t$, and let $K_3$ denote the triangle. A graph $F$ is $K_3$-Erdős–Simonovits when it satisfies the genera…

Let $K_{s,t}$ be the complete bipartite graph with part sizes $s$ and $t$, where $s\leq t$, and let $C_k(G)$ denote the $k$-coalition number of a graph $G$. Complete bipartite grap…

Let $K_{s,t}$ be the complete bipartite graph with parts of sizes $s$ and $t$. Complete bipartite monochromatic $k$-connection conjecture. For $t\ge s\ge k\ge 2$, … and, for…

For positive integers $a$ and $b$ with $a>b$, let $K_{a,b}$ denote the complete bipartite graph with parts of sizes $a$ and $b$, and let $\chi_c^\star$ denote its correspondence pa…

Let $K_{n,n}$ be the complete bipartite graph with $n$ vertices in each part. A 1-factorisation is a partition of the edges into 1-factors; the cycles of a 1-factorisation are the…

Let $K_{n,n}$ be the complete bipartite graph with $n$ vertices in each part. A 1-factorisation is a partition of the edges into 1-factors, and it is perfect when the union of ever…

List color threshold conjecture.

Consider a 3-edge-colouring of the complete bipartite graph $K_{n,n}$. A partition into monochromatic paths is a partition of all vertices into vertex-disjoint paths, each monochro…

For a graph $H$, write $sat(n,H)$ for the minimum number of edges in an $H$-saturated graph on $n$ vertices. Let $K_{3,3}$ denote the complete bipartite graph with parts of size…

Subdivision extremal bound conjecture. For any integers $s,t,k\geq1$,

Let $K(m,n)$ be the complete bipartite graph with part sizes $m$ and $n$, and let $k$-super graceful have the labeling meaning used in the paper. Complete-bipartite classification…

Odd-order Hamiltonian-face embedding conjecture. Theorem also holds for any odd integer $n\ge3$; that is, there is a 2-cell embedding of $K_{n,n}$ into $\mathbb{S}_{L(n)}$ having a…

Let $K_{m,n}$ be the complete bipartite graph with $m\ge n\ge 2$, and let $ub(G)$ denote the unit bar visibility number of a graph $G$. Asymptotic unit bar visibility conjecture. F…

Linear cycle-cover conjecture. There is a $c$ such that for every $r$, every $r$-local colouring of $K_n$ admits a covering with $cr$ disjoint monochromatic cycles. The same should…

Let $K_{n,m}$ be the complete bipartite graph. Denote its critical edge density by $d_{crit}(K_{n,m})=d(n,m)$ and the best edge density obtained from star decomposition by…

Complete-bipartite majority out-domination conjecture.

Aalipour-Hafshejani et al.'s conjecture. For all $a,b\in\mathbb{N}$, if $|a-b|\geq 2$, then ${\cal K}(a,b)$ is ${\cal D}$-unique; that is, every graph with the same domination poly…

Complete bipartite graph spy number conjecture. When $3$ divides $m$, $sigma(G,m,r)$ is approximately