46 problems

Thomassen's conjecture. Every such graph $G$ admits a crumby red-blue vertex coloring.

Let $G$ be a triangle-free graph with maximum degree at most $3$. Its fractional chromatic number $\chi_f(G)$ is the minimum of $a/b$ over all fractional $a/b$-colorings, where a f…

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…

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…

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 planar chemical graph, meaning a planar graph of maximum degree at most $3$. If the adjacency-matrix eigenvalues of an $n$-vertex graph are ordered as … let the median…

A crumby coloring of a graph is a red–blue vertex partition in which the blue vertices induce a graph of maximum degree at most one, while the red vertices induce a graph with no i…

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

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 connected graph of order $n(G)$ and maximum degree at most $3$, with girth at least $5$. A matching $M$ in $G$ is uniquely restricted if no other matching in $G$ cover…

Faudree et al.'s subcubic conjectures. begin{enumerate} item The strong chromatic index is at most $10$. item If $G$ is bipartite, then $\chiup_{s}'(G) \leq 9$. item If $G$ is plan…

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 subcubic graph, meaning that every vertex of $G$ has degree at most $3$, and let $G'$ be a subdivision of $G$. The packing chromatic number conjecture. The packing chr…

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

A subcubic graph is a graph $G$ with maximum degree $Delta(G)\leq 3$. An $(1^2,2^4)$-coloring is a partition of $E(G)$ into two matchings and four induced matchings. Hocquard–Lajou…

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…

Large-subcubic list strong coloring conjecture. If $G$ has at least $13$ vertices, then

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.

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