(1,2)-Factorizations of General Eulerian Nearly Regular Graphs

Summary

Every general graph with degrees 2k and 2k − 2,k ≥ 3, with zero or at least two vertices of degree 2k − 2 in each component, has a k-edge-colouring such that each monochromatic subgraph has degree 1 or 2 at every vertex.

In particular, if T is a triangle in a 6-regular general graph, there exists a 2-factorization of G such that each factor uses an edge in T if and only if T is non-separating.

Introduction

In this paper we will characterize those general graphs with degrees 2k − 2 and 2k that can be decomposed into spanning subgraphs with degrees 1 and 2 everywhere. Before we state the result, it is perhaps of some interest to review some related problems and their history.

Background

One of the starting points of graph theory is a classic investigation by the Danish mathematician Julius Petersen who in 1891 published a paper: ‘Die Theorie der regulären graphs’, which contains a wealth of material on the problem of factorizing regular graphs into graphs of uniform degree k. An excellent source of information concerning Julius Petersen and problems spawned by his 1891 paper is the conference volume.

The motivation for Petersen's work, as given in the first few lines of his article, came from Hilbert's proof of the finiteness of the system of invariants associated with a binary form.