Abstract: Planar
graphs with maximum degree 4 are either in Class 1 or in Class 2. The question
if the problem to decide whether these graphs belong to one of these classes is
NP-complete remains open. A probable answer is “yes”. Therefore, finding
categories of planar graphs with that are either 4-edge colourable or a 4-edge colouring
assignment exists for most of their edges is an interesting challenge. One
parameter to categorize these graphs is the distance between vertices of degree
4. Using this parameter the following result is getting: A planar connected and
bridgeless graph G,
with and having vertices of degree 4 whose distance is at least 5, is
in Class 1. A second result comes as a consequence of the first one providing us
by a procedure to assign a 4-edge colouring to “almost
all” the
edges of a 4-regular planar graph, with “large”
girth.
Actually we prove that: A connected bridgeless and planar 4-regular graph G,
with girth has a 4-edge colouring in edges, where n is
the order of G.
Therefore, the fraction of the number of the edges which get a 4-colouring to
the size of Gis
at least
Keywords and phrases: edge-colouring, 2-factors, NP-complete problems.
