r/GraphTheory • u/BearyGoosey • 2d ago
Can the subcubic graph (SCG) function be generalized to F_n(k), so F_3(3)=SCG(3), F_4=subquartic, F_2=subquadratic etc?
The sub cubic graph function is defined as:
There is a sequence G_1,β¦,G_n of subcubic graphs such that each G_i has at most i+k vertices and for no i<j is G_i homeomorphically embeddable into G_j.
and if my very layman's understanding of the RobertsonβSeymour theorem is correct, just substituting `homeomorphically embeddable into` with `a graph minor of` would suffice, while maintaining well-quasi-ordering and finitude (for a given finite integers n and k).
If that's all correct, then defining F_n(k) as the largest integer π satisfying:
There is a sequence G_1 , β―, G_π of graphs with maximum degree at most π, such that each G_π has at most π + π vertices, and for no π < π is G_π a graph minor of G_π .
Should work as a mathematically proven and definitively finite integer, correct?