Advances and Applications in Discrete Mathematics
Volume 1, Issue 2, Pages 171 - 185
(April 2008)
|
|
INEQUALITIES FOR THE TIMES WE HAVE TO USE THE FOURTH COLOR IN A 4-EDGE COLORING OF A CUBIC GRAPH
Diamantis Koreas (Greece)
|
Abstract: For a cubic graph G
let the following problem: “Among all proper 4-edge colorings of G
find one that minimizes the use of one of the four colors”. This paper deals
with this problem. We consider a 4-edge coloring of G
which minimizes the smallest cardinality m
of color classes. Using colors 1, 2, 3 and 4, let this class have the fourth
color “4”. We introduce a variable D
that denotes the distance between pairs of edges having color 4. We also
introduce another variable q, which is
related to the number of vertices that is necessary to delete, in order to get a
3-edge critical subgraph of G. Our
motivation is to give inequalities having parameters m, D and q.
Therefore, finding restricted classes of cubic graphs which guarantee that
parameters D or q must have specific
values, then we can get good upper bounds for the cardinality m.
Moreover, we believe that these inequalities are useful tools in the further
investigation of 3-edge critical graphs. |
Keywords and phrases: 3-edge coloring,
edge-critical graphs, NP-complete problems, max edge 3-coloring. |
|
Number of Downloads: 249 | Number of Views: 1045 |
|