Premium
Graph decomposition with applications to subdivisions and path systems modulo k
Author(s) -
Thomassen Carsten
Publication year - 1983
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190070215
Subject(s) - combinatorics , mathematics , modulo , bipartite graph , vertex (graph theory) , discrete mathematics , degree (music) , subdivision , graph , physics , archaeology , acoustics , history
The existence of a function α(k) (where k is a natural number) is established such that the vertex set of any graph G of minimum degree at least α(k) has a decomposition A ∪ B ∪ C such that G(A) has minimum degree at least k , each vertex of A is joined to at least k vertices of B , and no two vertices of B are separated by fewer than k vertices in G(G ∪ C). This is applied to prove the existence of subdivisions of complete bipartite graphs (complete graphs) with prescribed path lengths modulo k in graphs of sufficiently high minimum degree (chromatic number) and path systems with prescribed ends and prescribed lengths modulo k in graphs of sufficiently high connectivity.