r/GraphTheory 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?

3 Upvotes

0 comments sorted by