Advances and Applications in Discrete Mathematics
Volume 6, Issue 2, Pages 153 - 165
(October 2010)
|
|
THE DISTANCE BETWEEN CROSSING POINTS AS A PARAMETER IN EDGE COLORING PROBLEMS FOR CUBIC GRAPHS
Diamantis Koreas
|
Abstract: In this paper, we investigate the 3-edge coloring problem,
based on the idea to give an algorithm, that attempts to minimize the use of
color 4 (in a 4-edge coloring), and to study the factors that force it to fail.
More specific, we introduce the notion of the “position” of crossing points
(or crossing edges) and the notion of the “connection by bicolor paths”. A
first result of this approach is that we can always assign a 4-edge coloring in
a connected, bridgeless and cubic graph G using the fourth
color only in
crossing edges. Furthermore, color 4 is needed at most in half
of these pairs of crossing edges. Finally, we bound the number of times
color 4 is required in terms of the distance between the crossing points in the
drawing of the graph.
|
Keywords and phrases: graph coloring, planar graphs. |
|
Number of Downloads: 230 | Number of Views: 836 |
|