Graph decomposition with applications to subdivisions and path systems modulo k

✍ Scribed by Carsten Thomassen

• Publisher: John Wiley and Sons
• Year: 1983
• Tongue: English
• Weight: 585 KB
• Volume: 7
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190070215

✦ Synopsis

The existence of a function a(k) (where k is a natural number) is established such that the vertex set of any graph G of minimum degree at least a ( k ) has a decomposition A U B U C such that G(A) has minimum degree a t 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(B U 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.