1. Introduction
We consider the scheduling problems involving tasks
. If two tasks both use a common resource, they cannot be scheduled at the same time. A valid scheduling is a mapping f from
to the subsets of a time period [0,T] such that
if
and
use a common resource. Let the value of a scheduling f be
, which is the minimum length of time a task has been assigned normalized by the length of the time period. The goal is to find a scheduling
that maximizes
. One example of this type of scheduling problem is the heavily loaded resource sharing system in computer science [1-3]. The tasks are processes and some of them may share a common data file. Two processes that do share a common data file cannot operate at the same time. A scheduling of the processes that has the maximum value would allow the processes to operate most efficiently.
The constraints of the scheduling problem can be represented by a graph, called the conflict graph. The conflict graph G has vertex set
representing the tasks where two vertices vi and vj are adjacent if and only if they use at least one common resource. Vertex colouring and chromatic numbers of the conflict graph have been used as models for scheduling problems (see for example [4]). If G can be coloured with kcolours such that no two adjacent vertices have the same colour, we can then divide [0,T] into k equal length periods. All vertices that are coloured with the same colour do not have edges between them and therefore can be assigned to one period. For this scheduling f, we have
. Thus in general
.
When the tasks are periodic in nature, circular colouring of the conflict graph is a more appropriate method. Circular colouring and the circular chromatic number (also called the star chromatic number) were introduced by A. Vince in 1988 [5]. A (k,d)-circular-colouring of a graph G is a mapping
such that for each edge xy in G,
.
The circular chromatic number of G,
, is the infimum of the ratio k/d for which G has a (k,d)-circularcolouring.
Equivalently, we can consider a (k,d)-circular-colouring of G as a mapping c from V(G) to the open arcs of length d in a circle of length k such that if xy is an edge in G,
. If we assign the tasks using a (k,d)- circular-colouring of the conflict graph G, we would have
.
A (k,d)-set-colouring of a graph G is a mapping c such that for every vertex v in G, c(v) is a d-subset of
and if xy is an edge in G,
. The fractional chromatic number of a graph G,
, is the infimum of the ratio (k/d) for which G has a (k,d)-set-colouring. If we can consider a (k,d)-set-colouring as a mapping c from V(G) to the sets of arcs in the circle of length k such that the length of the union of arcs in f(v) is at least d for every vertex v and if xy is an edge inG,
. An assignment using a (k,d)-set-colouring of the conflict graph G would yield
.
Circular chromatic number and fractional chromatic number and their variations have been extensively studied in the last two decades [6-11]. More results on the circular chromatic number and fractional chromatic number can be found in the book [12] and the survey papers [13,14]. It is easy to see that by their definition, we have the relations
![](https://www.scirp.org/html/10-1200158\e2461e80-fdd1-4f91-aca4-4e6ffbe3c2dd.jpg)
Vince proved in [5] that
![](https://www.scirp.org/html/10-1200158\35745cdc-6950-46ec-8e22-2e283803efac.jpg)
Therefore, we have
![](https://www.scirp.org/html/10-1200158\96b158c4-2060-4915-8502-ec142a51bb55.jpg)
While the difference between
and
is always less than 1, it is known that the difference between
and
can be arbitrarily large for some graphs. An example is the family of graphs called Kneser graphs. A Kneser graph ([15,16])
has all q-subsets of
(p > 2q) as its vertices and two vertices are adjacent if the two subsets are disjoint. It is proved in [16] that
![](https://www.scirp.org/html/10-1200158\902776b5-e31a-4913-9959-98c813a723d5.jpg)
![](https://www.scirp.org/html/10-1200158\40b68aa4-1670-4e4b-be39-1f4d6e667eba.jpg)
Another example of a family of graphs where the difference between their chromatic number and fractional chromatic number is large is the graphs obtained by using Mycielski’s construction.
For a graph G with vertex set
and edge set
, the Mycielskian
of G is the graph with vertex set
and edge set
.
in
Figure 1 is also called the Grotzsch graph.
It is well known that
![](https://www.scirp.org/html/10-1200158\b6e49028-1971-4802-bdd9-57a451ca9d2e.jpg)
For the fractional chromatic number of Mycielskians, the authors of [17] found the recurrence relation
![](https://www.scirp.org/html/10-1200158\62073812-2c4f-480a-8859-cc39f32d6463.jpg)
For the Grotzsch graph, since
we have
![](https://www.scirp.org/html/10-1200158\69418b9e-952c-4d71-a735-1960ac7ec4f3.jpg)
We use the notation
such that
![](https://www.scirp.org/html/10-1200158\b2653539-0ab4-481a-9c49-39d24f1bc54e.jpg)
We have
![](https://www.scirp.org/html/10-1200158\a9768fac-4243-4479-be87-8425df7b101b.jpg)
In comparison, we have
![](https://www.scirp.org/html/10-1200158\15998fbd-b9f6-4fdc-8cfa-343de0b8b18a.jpg)
For this class of graphs, the difference between
and
is unbounded.
For the circular chromatic number, we have
![](https://www.scirp.org/html/10-1200158\3590e2d8-21b9-460a-ad84-9a0364c4951d.jpg)
This shows that the difference between the circular chromatic number and the fractional chromatic number is also arbitrarily large for the Mycielskians. To achieve the optimal result for a scheduling problem in general, it appears that the fractional chromatic number of the conflict graph provides the best results.
However, there are difficulties if we use (k,d)-set colouring and the fractional chromatic number in the scheduling problem. To achieve
the optimal (k,d)-set colouring may have a very large value of d. As pointed out in [12],
is an example of a graph G for which
for no small d. In fact, if we let
and
, then
![](https://www.scirp.org/html/10-1200158\aa99ed8c-47e1-4f9c-b301-d8de5306bc74.jpg)
and
is a fraction whose denominator, when written in smallest terms, is greater than
. This example shows that there is no bound on the denominator of
that is a polynomial function of the number of vertices of G. If this optimal set colouring is to be used for scheduling, each task would be divided into too many fragments making it impossible in practice. To combine optimality and practicality, in the next section we propose a new colouring of the conflict graph that will provide a better solution than the circular colouring and easier to implement than the set colouring.
2. Multiple Circular Colouring of a Graph
Definition 1 An m-(k,d)-circular colouring of a graph G is a mapping c from V(G) to the sets of open arcs in the circle of length k such that c(v) is the union of m arcs with a total length at least d and if xy is an edge in G,
The m-circular chromatic number,
is the infimum of the ration
for which Ghas a m-(k,d)-circular-colouring.
It is easy to see that for every positive integer m,
![](https://www.scirp.org/html/10-1200158\7f3545f9-07bd-4f23-8215-5b179a993350.jpg)
To demonstrate this colouring indeed improves the solution of the scheduling problem in some cases, we show that even for
,
can be strictly less than
for large classes of graphs.
Recall that for a graph G, M(G) is the Mycielskian of G. There are many graphs G such that
Some sufficient conditions for this equality to hold are given in, for example, [18] and [19]. However,
will always be strictly less than
.
Theorem 2 For every graph G,
![](https://www.scirp.org/html/10-1200158\45df3182-5a07-48ac-a8b4-4691e753c244.jpg)
Proof: Let
and
as described in the previous section. Let
be a circle of length k. Since
, there is a mapping of the form
for each i where
such that
whenever
and
are adjacent.
Let
be a circle of length
. Let
. Notice that ![](https://www.scirp.org/html/10-1200158\e9cad2b3-1e82-4336-9ad9-acaa544dda93.jpg)
for all i. Figure 2 demonstrates this mapping when
.
For each i, if
, let
;
otherwise, let
We show that the arcs representing these vertices in the case of
in Figure 3.
It is easy to check that this is a valid 2-
-circular colouring of M(G) in general. This proves that
![](https://www.scirp.org/html/10-1200158\6bad55ac-4ab3-442a-abf3-4cfd3b4ba721.jpg)
Corollary 3 If
then
![](https://www.scirp.org/html/10-1200158\b6b200b1-d2af-4dcf-bc6d-cfb8914f8cfc.jpg)
Next we show that unlike the set-chromatic number, the denominator of the m-circular chromatic number is bounded by the product of m and the number of vertices in the graph.
![](https://www.scirp.org/html/10-1200158\aa4526d8-3b0c-48c5-965f-c75af9a76e89.jpg)
Figure 2. A 2-circhular coloring of vertices of C5 and w in M (C5).
![](https://www.scirp.org/html/10-1200158\cafd68eb-6739-4a58-91c3-9a0c15440cc3.jpg)
Figure 3. A 2-circular coloring of M (C5).
Theorem 4 Let G be a graph of n vertices, and
Then k and d can be integers such that d <
mn.
Proof: Suppose that
By scaling if necessary, there is a m-circular colouring c that maps the vertices of G to sets of m arcs in a circle of length r such that each arc has length at least
and if xy is an edge then
We assume that c is a colouring such that the set
![](https://www.scirp.org/html/10-1200158\3be1f9af-6e67-4c24-869b-21ee02bcc696.jpg)
is the smallest. We fix a direction of the circle, say counter clockwise.
There is at least one arc l such that
; otherwise r could be made smaller. Let that arc be l1. There must be an arc
such that i)
is adjacent to
in G, ii) the left end of l1 is the right end of
and iii)
, otherwise
could be made larger.
Continuing this process, some arc will have to be used more than once. Say the first time this happens is at
. Then the arcs
must cover the circle an integer number of times. Suppose that they cover the circle s times. Since there are
arcs and they all have length
, we have
![](https://www.scirp.org/html/10-1200158\12104439-9086-4c68-8fd5-5c952674dea0.jpg)
and
![](https://www.scirp.org/html/10-1200158\96bf583f-6946-4e58-afbb-33c9b61d612c.jpg)
Since
, the denominator is less than mn.
Intuitively, when the value of m increases, the m-circular chromatic number will be closer to the fractional chromatic number and thus the difference between the chromatic number and m-circular chromatic number would increase. Nevertheless, our next theorem shows that the m-circular chromatic number cannot be less than one m-th of the .chromatic number.
Theorem 5 For every graph G, ![](https://www.scirp.org/html/10-1200158\3efc0851-9476-41ce-990f-f286ff1a2e0c.jpg)
Proof: Suppose that
There is an m-circular colouringc such that
for every vertex v.
Since c(v) is a union of m arcs, at least one of the arcs has length at least
. We insert mr points ![](https://www.scirp.org/html/10-1200158\cb2f287f-59ca-47bf-81a6-e80fa53a6bff.jpg)
spaced at equal distance in the unit length circle. For every vertex v, c(v) contains at least one of these points. Let
Each
is an independent set and
. G can be coloured with mrcolours. So we have
![](https://www.scirp.org/html/10-1200158\507f6726-5a53-4cb8-8db6-987d4eddbe7a.jpg)
i.e., ![](https://www.scirp.org/html/10-1200158\19b6dca1-a906-40a6-a62f-83f8812905b0.jpg)
The Kneser graphs provide examples showing this lower bound is asymptotically the best possible.
Let
be the independence number of G.
is also bounded by a function of
. The proof above yields a lower bound for
.
Theorem 6 For every graph G with n vertices,
![](https://www.scirp.org/html/10-1200158\cdfb67d5-63f5-4d04-a9ab-f747b4f2a2be.jpg)
Proof: The set
in the proof of Theorem 5 is an independent set. We have
such independent sets. The average size of one set is
Therefore
![](https://www.scirp.org/html/10-1200158\64dc7782-4341-446e-8e78-c729ba1399b2.jpg)
and
![](https://www.scirp.org/html/10-1200158\6f7b7300-4385-423e-a39e-ce1d77301884.jpg)
3. Conclusion
We proved that for a large class of graphs, this multiple circular colouring and m-circular chromatic number of the conflict graph will provide better solutions for the scheduling problem than the original circular chromatic number. It is also easier to implement than the model using the fractional chromatic number. We plan to investigate more classes of graph G where
for small values of m. It would also be interesting to find out the probability for random graphs to have m-circular chromatic number strictly less than their circular chromatic number.