Advances and Applications in Discrete Mathematics
Volume 18, Issue 3, Pages 317 - 330
(July 2017) http://dx.doi.org/10.17654/AADMJul2017_317_330 |
|
ON 4-EDGE COLORING OF CUBIC GRAPHS CONTAINING “SMALL” NON-PLANAR SUBGRAPHS
Diamantis Koreas
|
Abstract: The problem we deal with is to find the minimum size of the four color classes among all proper 4-edge colorings of a cubic graph G. The bound for the number t of times that color 4 is required given in [8] is modified for the case of cubic graphs G having subgraphs that contain all the crossing points with l connected edges common to the rest of graph. The new bound becomes much better than the previous one if the fraction of the order of subgraphs to the order of whole G is “small” or if the number of connected edges l is “small”. |
Keywords and phrases: edge coloring, max-3-edge coloring. |
|
Number of Downloads: 338 | Number of Views: 1148 |
|