36 problems

MED decomposition conjecture. Every 2-connected graph with maximum degree 3 has a MED decomposition.

Let $G$ be a claw-free subcubic graph. Seven-color packing coloring conjecture. The graph $G$ is $(2,2,2,2,2,2,2)$-packing colorable. The paper gives related packing-coloring resul…

Let $G$ be a claw-free subcubic graph, and let $\mathcal{G}_{11}$ be the graph specified in the paper. Exceptional packing coloring conjecture. If $G\neq\mathcal{G}_{11}$, then $G$…

Let $G$ be a $(3,0)$-saturated subcubic graph, and let $g_3(G)$ denote its local girth parameter. Packing coloring conjecture. If … then $G$ is $(1,1,2)$-packing colorable. The pap…

Let $G$ be a $2$-saturated subcubic graph. Five-color packing coloring conjecture. The graph $G$ is $(1,2,2,2,2)$-packing colorable. The paper proves a four-color variant when…

Let $G$ be a $0$-saturated subcubic graph, and let $g_3(G)$ denote its local girth parameter. Packing chromatic number conjecture. If … then … The paper proves the corresponding up…

A packing $(1,1,2,3)$-coloring is a partition of the vertex set into four classes whose pairwise vertex distances are respectively at least $2$, $2$, $3$, and $4$. Gastineau–Togni…

A packing $(1,1,2,2)$-coloring of a graph is a partition of its vertex set into four classes whose pairwise vertex distances are respectively at least $2$, $2$, $3$, and $3$. Liu–Z…

For a graph $G$, its 1-subdivision is obtained by replacing every edge with a path of two edges. The packing chromatic number $\chi_p(G)$, or PCN, is the smallest positive integer…

Let $G$ be a graph in which every vertex has degree at most $3$, and let $S(G)$ be the graph obtained by subdividing every edge of $G$, replacing each edge $uv$ by a path $u$-$w$-…

Let $G$ be a subcubic graph, meaning that every vertex of $G$ has degree at most $3$, and let $\chi'_{st}(G)$ denote the minimum number of colors in a proper edge-coloring of $G$ w…

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 maximum degree at most three, and let $\chi^\prime_s(G)$ denote its star chromatic index, the smallest number of colors in a proper edge coloring in which no…

Subdivision packing-coloring conjecture. The graph $S(G)$ admits a $(1,2,3,4,5)$-packing coloring. Equivalently, every subdivision of a subcubic graph has packing chromatic number…

Let $G$ be a finite graph. A set $C\subseteq V(G)$ is a locating-dominating set if it dominates every vertex outside $C$ and, for every two distinct vertices…

The $(1,2^7)$-edge-coloring conjecture. Every subcubic graph is $(1,2^7)$-edge-colorable.

Triangle-free subcubic bisection conjecture. Every weighted triangle-free subcubic graph other than $K_{1,3}$ has a bisection of weight at least

Let $G$ be a connected subcubic planar graph, and for $i\in\{0,1,2,3\}$ let $n_i(G)$ denote the number of vertices of degree $i$ in $G$. Let $\gamma(G)$ denote the domination numbe…

Let $G$ be a simple graph of order $n$, and let its adjacency eigenvalues be … A graph is subcubic if its maximum degree is at most $3$, and it is planar if it can be drawn in the…

Henning–Löwenstein–Rautenbach conjecture. Every connected subcubic graph $G$ except the three graphs $H_1$, $H_2$, and $H_3$ satisfies

Let $G$ be a subcubic graph. Stronger subcubic conjectures. (a) If $G$ is bridgeless and is neither the Wagner graph nor the graph formed from $K_{3,3}$ by subdividing one edge, th…

A graph is decomposable if it admits a locally irregular edge-coloring (LIEC), and let $\chi_{\mathrm{irr}}'(G)$ denote the smallest number of colors in a LIEC of a decomposable gr…

A crumby coloring is a red-blue vertex coloring in which the blue subgraph has maximum degree at most $1$ and the red subgraph has minimum degree at least $1$ and contains no path…

A crumby coloring is a red-blue vertex coloring in which the blue subgraph has maximum degree at most $1$ and the red subgraph has minimum degree at least $1$ and contains no path…

Let $G$ be a weighted triangle-free graph with maximum degree at most $3$; equivalently, $G$ is a weighted triangle-free subcubic graph. Weighted subcubic conjecture. One should ha…