Independence Bounds for Sparse Subcubic Graphs

Definitions and mathematical statement

The supplied bound is \[ 2a(G)\geq n(G)-m(G) \] for graphs with no $C_3$ or $C_4$ and maximum degree at most $3$. Under the usual finite simple graph convention, $C_j$ is a cycle of length $j$, $\Delta(G)=\max_v\deg_G(v)$, and the absence of $C_3,C_4$ means girth at least $5$, with forests assigned infinite girth. The conventional meaning $n(G)=|V(G)|$ is available, but the record does not define $a(G)$ or $m(G)$.

This matters because the registry title says "Independence Bounds," while the literature assessment describes induced forests. The two natural invariants are different: \[ \alpha(G)=\max\{|S|:S\subseteq V(G),\ G[S]\text{ has no edges}\}, \] \[ a_{\mathrm{forest}}(G)=\max\{|S|:S\subseteq V(G),\ G[S]\text{ is acyclic}\}. \] Neither is silently identified with the source's $a(G)$. Similarly, although $m(G)$ often denotes $|E(G)|$, the record does not explicitly assign that meaning. The displayed inequality must retain its symbols until the original invariant definitions are recovered.

The three requests are to determine an extension or improvement for larger girth, to determine an extension when the maximum-degree bound is removed, and to determine the extremal graphs. In the first direction the intended girth threshold, parameter-dependent formula and whether $\Delta\leq3$ remains fixed need specification. Simply restricting to larger girth inherits any valid original inequality; the question may therefore seek a sharper bound, but no sharp formula is supplied. In the second direction the surviving cycle restriction and any substitute sparsity or degree-dependent condition must be fixed. "Extremal" could mean equality in the displayed inequality, \[ 2a(G)=n(G)-m(G), \] or sharpness/equality for a new extended bound; these are distinct classification tasks.

The literature triage checked 2026-08-21 reports the larger-girth, unrestricted-degree and extremal questions in the induced-forest context and no complete resolution of that broad list. The verification note reports only normalization of invariant, cycle and degree notation. The open label does not resolve the conflict between the title and background or establish the missing definitions, and is retained as dated metadata.

Short English statement

Extend the stated sparse-subcubic graph bound to larger girth and to unrestricted degree, and classify the relevant extremal graphs. The source does not define $a(G)$ or $m(G)$, and its title refers to independence while its assessment refers to induced forests. Those different invariants must be resolved before a precise strengthened bound can be selected.

Sources

• Local UnsolvedMath registry, permanent ID 30000416, source code catalogue entry, "Independence Bounds for Sparse Subcubic Graphs," including the displayed inequality, both requested extensions, extremal question and induced-forest literature description.
• Algorithmic Graph Theory (2006), Oberwolfach Reports, pp. 379--460, DOI 10.4171/owr/2006/07: https://doi.org/10.4171/owr/2006/07.
• Supplied reference "related list-coloring research": https://doi.org/10.1002/jgt.20326.
• Literature triage checked 2026-08-21; local record updated 2026-09-16. No external source has been visited or independently checked here.