![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
The notion of the b-chromatic number of a graph attracted much research interests and recently a new concept, namely the b-chromatic sum of a graph, denoted by , has also been introduced. Motivated by the studies on b-chromatic sum of graphs, in this paper we introduce certain new parameters such as
-chromatic sum,
-chromatic sum,
-chromatic sum,
-chromatic sum and
-chromatic sum of graphs. We also discuss certain results on these parameters for a selection of standard graphs.
Public Interest Statement
Graph colouring attracted wide interest among researchers since its introduction in the second half of the nineteenth century. Initial studies regarded colours to be distinct in terms of the corresponding numbering of subscripting of colours only. A number of interesting extremal graph theoretic problems were researched well. Colouring sums are more recent and allows for applications where colours may be technologies of kind with some relation between the distinct technologies. It is envisaged that colour products and other mathematical relations between colours will naturally follow as enhanced research fields. It is foreseen that the modelling of metabolic or artificial intelligent structures as “colours” within larger real or virtual living structures of which certain components are modelled as graphs will reveal interesting applications.
1. Introduction
For general notations and concepts in graph theory and digraph theory, we refer to Bondy and Murty (Citation1976), Chartrand and Lesniak (Citation2000), Chartrand and Zhang (Citation2009), Gross and Yellen (Citation2006), Harary (Citation1969), West (Citation2001). Unless mentioned otherwise, all graphs mentioned in this paper are non-trivial, simple, connected, finite and undirected graphs.
Graph colouring has become a fertile research area since its introduction in the second half of nineteenth century. It has numerous theoretical and practical applications. Let us first recall the fact that in a proper colouring of a graph G, no two adjacent vertices in G can have the same colour. The minimum number of colours in a proper colouring of a graph G is called the chromatic number of G, denoted by .
Consider a proper k-colouring of a graph G and denote the set of k colours by . Also, consider the disjoint subsets of V(G), defined by
,
. Clearly, we can see that
.
The notion of the b-colouring of a graph and the parameter b-chromatic number, , of a graph G(V, E), has been introduced in Irving and Manlove (Citation1999) as follows. Let G be a graph on n vertices, say
. The b-chromatic number of G is defined as the maximum number k of colours that can be used to colour the vertices of G, such that we obtain a proper colouring and each colour i, with
, has at least one element
which is adjacent to a vertex of every colour j,
. Such a colouring is called a b-colouring of G (see Effatin & Kheddouci, Citation2003; Irving & Manlove, Citation1999).
The concept of b-chromatic number has attracted much attention and many studies have been made on this parameter (see Effatin & Kheddouci, Citation2003; Irving & Manlove, Citation1999; Kok & Sudev, Citationin press; Kouider & Mahéo, Citation2002; Vaidya & Isaac, Citation2014; Vaidya & Isaac, Citation2015; Vivin & Vekatachalam, Citation2015).
2. General colouring sum of graphs
The notion of the b-chromatic sum of a given graph G, denoted by , has been introduced in Lisna and Sunitha (Citation2015) as the minimum of sum of colours c(v) of v for all
in a b-colouring of G using
colours. Some results on b-chromatic sums proved in Lisna and Sunitha (Citation2015), which are relevant and useful results in our present study, are listed below.
Theorem 2.1
(Lisna & Sunitha, Citation2015) The b-chromatic sum of a path ,
is
Theorem 2.2
Lisna & Sunitha, Citation2015 The b-chromatic sum of a cycle is given by
Theorem 2.3
Lisna & Sunitha, Citation2015 The b-chromatic sum of a wheel graph is
Theorem 2.4
Lisna & Sunitha, Citation2015 For a complete bipartite graph assume without loss of generality that
, then
.
This interesting new invariant motivates us for studying similar concepts in graph colouring. This leads us to define the concept of the general colouring sum of graphs as follows.
Definition 2.5
Let allows a b-colouring
of a given graph G. Clearly, there are k! ways of allocating the colours to the vertices of G. The colour weight of colour, denoted by
, is the number of times a particular colour
is allocated to vertices. Then, the colouring sum of a colouring
of a given graph G, denoted by
, is defined to be
.
In view of the above definition, the b-chromatic sum of a graph G can be viewed as , where this sum varies over all b-colourings of G.
In view of Definition 2.5, in this paper we introduce certain other colouring sums of graphs similar to the b-chromatic sum of graphs.
3. ![](//:0)
-Chromatic sum of certain graphs
The notion of the -chromatic sum of a graph G with respect to a proper k-colouring of G is introduced as follows.
Definition 3.1
Let be a proper colouring of a graph G. Then, the
-chromatic sum of G, denoted by
, is defined as
where the sum varies over all minimum proper colourings of G.
In the following discussion, we investigate the -chromatic sum of certain fundamental graph classes. First, we determine the
-chromatic sum of path graphs in the following theorem.
Theorem 3.2
The -chromatic sum of a path
is given by
Proof
Being a bipartite graph, the vertices of a path graph can be coloured using two colours, say
and
. Then, we need to consider the following cases.
(i) | Assume that | ||||
(ii) | Let n be an even integer. Then, the vertices of path | ||||
(iii) | Let |
In a similar way, the -chromatic sum of a cycle graph
can be determined as follows.
Theorem 3.3
The -chromatic sum of a cycle
is
.
Proof
Let be a proper colouring of the cycle
. If n is even,
must contain at least two colours, say
and
and if n is odd, then
must contain at least three colours, say
and
. Then, we consider the following cases.
(i) | Let n be an odd integer. Now, we can assign the colour | ||||
(ii) | Let n be an even integer. Then, as explained in the previous result, we can assign the colour |
A wheel graph, denoted by , is defined to be the join of a cycle
and a trivial graph
. That is,
. The
-chromatic sum of a wheel graph is determined in the following theorem.
Theorem 3.4
The -chromatic sum of a wheel graph
is given by
Proof
Let us denote the central vertex of the wheel by v and the vertices of the outer cycle of
by
. Let
be a minimal proper colouring of
. Then,
must contain three colours, say
, if n is even and it must contain four colours, say
, if n is odd. Hence, we have the following two cases.
(i) | Let n be an even integer. Then, in the outer cycle, | ||||
(ii) | Let n be an odd integer. Then, in the outer cycle |
The following result describes the -chromatic sum of a complete graph
.
Proposition 3.5
The -chromatic sum of a complete graph
is
.
Proof
We know that in a proper colouring of , every vertex has distinct colours. That is,
. Therefore,
, for all
. Hence, we have
.
The -chromatic sum of a complete bipartite graph is determined in the following result.
Proposition 3.6
The -chromatic sum of a complete bipartite graph
,
is
.
Proof
Assume that G be the complete bipartite graph with a bipartition (X, Y) such that . As a bipartite graph, G is 2-colourable. Since
, label every vertex in X by the colour
and every vertex of Y by the colour
. Hence,
and
. Therefore,
.
Let us now recall the definition of a Rasta graph defined in Kok, Sudev, and Sudev (Citationin press) as follows.
Definition 3.7
(Kok et al., Citationin press) For a l-term sum set with
, define the directed graph
with vertices
and the arcs,
and
.
In Kok and Sudev (Citationin press), it is shown that for a Rasta graph R corresponding to the underlying graph of the chromatic number
. Assume, without loss of generality, that
if l is even and
if l is odd. Then, the
-chromatic sum of R is determined in the following theorem.
Theorem 3.8
The -chromatic sum of a Rasta graph R is given by
Proof
(i) | Let l be an even integer. Since all vertices corresponding to | ||||
(ii) | Let l be an odd integer. Then, as explained in the above case, the |
4. The ![](//:0)
-chromatic sum of certain graphs
We now define a new colouring sum, namely -chromatic sum of a given graph G as follows.
Definition 4.1
Let be a proper colouring of a graph G. Then, the
-chromatic sum of a graph G, denoted by
, is defined as
, where the sum varies over all minimum proper colourings of G.
Analogous to the studies on -chromatic sum of certain graphs, here we study the
-chromatic sum of the corresponding graphs.
Theorem 4.2
For , the
-chromatic sum of a path
is given by
Proof
If , we can assign
to its unique vertex, which shows that
. Hence, let
. As stated earlier, every path
is 2-colourable. Then, we have to consider the following cases.
(i) | If n is even, as mentioned in Theorem 3.2, the vertices can be coloured alternatively by the colours | ||||
(ii) | If n is odd, then the mutually non-adjacent |
The following is an immediate consequence of Theorem 3.2 and Theorem 4.2.
Corollary 4.3
For a path ,
it follows that,
if
or even, else
.
In the following result, let us determine the -chromatic sum of cycles.
Theorem 4.4
The -chromatic sum of a cycle
is given by
Proof
As stated earlier, if n is even, then is 2-colourable and if n is odd,
is 3-colourable. Then, we have to consider the following cases.
(i) | Let n be an even integer. Then, the vertices of | ||||
(ii) | Let n be an odd integer. Then, we can assign colour |
The following theorem describes the -chromatic sum of a wheel graph
.
Theorem 4.5
The -chromatic sum of a wheel graph
is given by
Proof
Let be the vertices of the outer cycle the wheel graph and v be its central vertex. We have already mentioned in Theorem 3.4 that if n is even, then
is 3-colourable and if n is odd, then
is 4-colourable. Then, we have the following cases.
(i) | Let n be an even integer. Then, we can assign the colour | ||||
(ii) | Let n be an odd integer. Then, we can assign colour |
The following result is an obvious and straightforward result on the -chromatic sum of complete graphs.
Proposition 4.6
The -chromatic sum of a complete graph
is given by
.
Proof
Note that and hence as mentioned in Theorem 3.8, all vertices have distinct colours. That is, we have
; for all
. Hence,
.
An obvious and straightforward result on the -chromatic sum of complete bipartite graphs is given below.
Theorem 4.7
Consider the -chromatic sum of a complete bipartite graph
,
,
.
Proof
Since the maximum sum is obtained by allocating colour
to the n non-adjacent vertices and
to the m non-adjacent vertices. So
and
. Therefore,
.
The -chromatic sum of Rasta graph can be determined as in the following theorem.
Theorem 4.8
The -chromatic sum of Rasta graph R is given by
Proof
(i) | Let l be an even integer. Since all | ||||
(ii) | If l is an odd integer, then the |
5. ![](//:0)
-Chromatic Sum of Certain Graphs
Analogous to the -chromatic sum and
-chromatic sum of graphs, we can also define the
chromatic sum as follows.
Definition 5.1
The -chromatic sum of a graph G, denoted by
, is defined as
, where the sum varies over a minimal b-colouring using
colours.
Now, for determining the respective values of for different graph classes, we use the proof techniques followed in Lisna and Sunitha (Citation2015). Reversing the colouring pattern explained in Lisna and Sunitha (Citation2015), we work out the
-chromatic sum of given graph classes. Hence, we have the following results.
Theorem 5.2
The -chromatic sum of a path
is given by
Proof
We know that a b-colouring of a path requires at most three colours. If
, the b-chromatic number of
is 2. In this context, the following cases are to be considered.
(i) | Let n be even. That is, | ||||
(ii) | Let |
(iii) | Let | ||||
(iv) | Let |
Similarly, the -chromatic sum of a cycle
is determined in the following theorem.
Theorem 5.3
The -chromatic sum of a cycle
is given by
Proof
First, let . It is to be noted that the b-chromatic number of the cycle
is 2, where the vertices
and
have colour
and the vertices
and
have the colour
. Therefore, the
-chromatic sum of
is
.
Next, assume that . We know that the b-chromatic number of a cycle
is 3. Let
be a b-colouring of a given cycle
. Here, we have to consider the following cases.
(i) | Let n be odd. Now a b-colouring which forms the colour classes, | ||||
(ii) | Let n be even. Now, a b-colouring which forms the colour classes, |
Now, the -chromatic sum of a wheel graph
is determined in the following result.
Theorem 5.4
The -chromatic sum of a wheel graph
is given by
Proof
We have already stated that the b-chromatic number of the cycle is 3. Therefore, a b-colouring of
must contain 3 colours, say
and
. Let the corresponding colour classes be
and
, where v is the central vertex of the wheel graph. Then,
,
and
. Hence,
. Next, assume that
. Then, every b-colouring of
must contain 4 colours. Let
be the required colouring of G. Then, we have to consider the following cases.
(i) | Assume that n is odd. Then, colour the vertices of | ||||
(ii) | Assume that n is even. Colour the vertices of |
The following theorem describes the -chromatic number of a complete bipartite graph.
Theorem 5.5
The -chromatic sum of a complete bipartite graph
is
.
Proof
The result follows directly from the proof of Theorem 4.7.
The b-chromatic sum and the -chromatic sum of Rasta Graph R is determined in the theorem given below.
Theorem 5.6
The b-chromatic sum of a Rasta graph R is given by
and the -chromatic sum of R is given by
Proof
The proof follows directly from the proofs of Theorem 3.8 and 4.8.
6. Two Thue chromatic sums of a path
A finite sequence of symbols of any alphabet is known to be non-repetitive if for all its subsequences
, the condition
, holds.
Let G be a simple undirected graph on n vertices and let a minimum set of colours allow a proper vertex colouring of G. If the sequence of vertex colours of any path of even and finite length in G is non-repetitive, then this proper colouring is said to be a Thue colouring of G (see Alon, Grytczuk, Hauszczak & Riordan, Citation2002).
The Thue chromatic number of G, denoted , is defined as the minimum number of colours required for a Thue colouring of G.
It is known that ,
and for
,
. Determining
is a hard problem, hence the problem is very hard for graphs in general.
The following lemma is the motivation for our further discussions in this paper.
Lemma 6.1
Škrabul’áková, Citationin press Up to equivalence, there is exactly one non-repetitive 3-colouring of the cycle .
In view of this lemma, we restrict our further discussion to the path . Let the vertices of
be labelled from left to right to be
. Recall that the colouring sum of a colouring
is defined by
. The possible minimum Thue colourings of
are listed below.
(i) |
| ||||
(ii) |
| ||||
(iii) |
| ||||
(iv) |
| ||||
(v) |
| ||||
(vi) |
| ||||
(vii) |
| ||||
(viii) |
| ||||
(ix) |
| ||||
(x) |
| ||||
(xi) |
| ||||
(xii) |
| ||||
(xiii) |
| ||||
(xiv) |
| ||||
(xv) |
| ||||
(xvi) |
| ||||
(xvii) |
| ||||
(xviii) |
| ||||
(xix) |
| ||||
(xx) |
| ||||
(xxi) |
| ||||
(xxii) |
| ||||
(xxiii) |
| ||||
(xxiv) |
|
Conjecture 6.2
For a path , there is a unique permutation over all proper b-colourings for which
is obtained, and exactly two permutations for which
is obtained.
The following general result is of importance for all variations of colouring sums discussed thus far. It holds for improper colourings as well. A general colouring which meets some general colouring index is called the -chromatic number of G and denoted,
.
Theorem 6.3
(Makungu’s TheoremFootnote1) If the set of colours allows a general colouring,
,
of G, such that
-colourings of
, then
.
Proof
Since for it follows that
, it follows through immediate induction that if
then for permuted one-on-one allocations of the elements in
to form
we have,
and
. Hence, if a
-colouring of G is allowed by
such that,
then,
and
.
Acknowledgements
The authors gratefully acknowledge the contributions of anonymous referees whose critical and constructive comments played a vital role in improving the quality and presentation style of the paper in a significant way.
Additional information
Funding
Notes on contributors
Johan Kok
Johan Kok is registered with the South African Council for Natural Scientific Professions (South Africa) as a professional scientist in both Physical Science and Mathematical Science. His main research areas are in Graph Theory and the reconstruction of motor vehicle collisions.
N.K. Sudev
N.K. Sudev has been working as a Professor (Associate) in the Department of Mathematics, Vidya Academy of Science and Technology, Thrissur, India, for the last fifteen years. His primary research areas are Graph Theory and Combinatorics.
K.P. Chithra
K.P. Chithra is an independent researcher in Mathematics. Her primary research area is also Graph Theory.
Notes
1 The first author dedicates this theorem to Makungu Mathebula and he hopes this young lady will grow up with a deep fondness for mathematics.
References
- Alon, N., Grytczuk, J., Hauszczak, M., & Riordan, O. (2002). Non-repetitive colourings of graphs. Random Structures & Algorithms, 21, 336–346. doi:10.1002/rsa.10057
- Bondy, J. A., & Murty, U. S. R. (1976). Graph theory with applications. London: Macmillan Press.
- Chartrand, G., & Lesniak, L. (2000). Graphs and digraphs. Boca Raton, FL: CRC Press.
- Chartrand, G., & Zhang, P. (2009). Chromatic graph theory. Boca Raton, FL: CRC Press.
- Effatin, B., & Kheddouci, H. (2003). The b-chromatic number of some power graphs. Discrete Mathematics & Theoretical Computer Science, 6, 45–54.
- Gross, J. T., & Yellen, J. (2006). Graph theory and its applications. Boca Raton, FL: CRC Press.
- Harary, F. (1969). Graph theory. Philippines: Addison Wesley.
- Irving, R. W., & Manlove, D. F. (1999). The b-chromatic number of a graph. Discrete Applied Mathematics, 91, 127–141.
- Kok, J., Sudev, N. K., & Sudev, C. (in press). On the curling number of certain graphs. arXiv: 1506.00813v2.
- Kok, J., & Sudev, N. K. (in press). The b-chromatic numbers of certain graphs and digraphs. arXiv: 1511.00680.
- Kouider, M., & Mahéo, M. (2002). Some bounds for the b-chromatic number of a graph. Discrete Mathematics, 256, 267–277.
- Lisna, P. C., & Sunitha, M. S. (2015). b-Chromatic sum of a graph. Discrete Mathematics, Algorithms and Applications, 7(3), 1–15. doi:10.1142/S1793830915500408
- \v{S}krabul’\’{a}kov\’{a}, E. (in press). Thue choice number versus Thue chromatic number of graphs. arXiv:1508.02559v1.
- Vaidya, S. K., & Isaac, R. V. (2014). The b-chromatic number of some path related graphs. International Journal of Computing Science and Mathematics, 4, 7–12.
- Vaidya, S. K., & Isaac, R. V. (2015). The b-chromatic number of some graphs. International Journal of Mathematics and Soft Computing, 5, 165–169.
- Vivin, J. V., & Vekatachalam, M. (2015). On b-chromatic number of sunlet graph and wheel graph families. Journal of the Egyptian Mathematical Society, 23, 215–222.
- West, D. B. (2001). Introduction to graph theory. Delhi: Pearson Education.