Advances and Applications in Discrete Mathematics
Volume 13, Issue 1, Pages 71 - 83
(January 2014)
|
|
NEW BOUND FOR THE NUMBER OF TIMES COLOR 4 IS REQUIRED, IN TERMS OF THE DISTANCE BETWEEN THE CROSSING POINTS, IN THE DRAWING OF A CUBIC GRAPH
Diamantis Koreas
|
Abstract: This paper deals with the following problem. “Among all proper 4‑edge colorings of a cubic graph G, with colors 1, 2, 3 and 4, find one that minimizes the use of color 4.” In a previous paper [1], this problem is faced using the notion of the “position” of crossing points (or crossing edges) and the notion of the “connection by bicolors paths”. Moreover, a bound is given of the number of times color 4 is required, in terms of the distance between the crossing points in the drawing of the graph. In the present paper, we improve this bound for specific types of cubic graphs. |
Keywords and phrases: edge coloring. |
|
Number of Downloads: 215 | Number of Views: 644 |
|