A note on δ^(k)-colouring of the Cartesian product of some graphs

Document Type : Original paper

Authors

1 Christ University, Bangalore, India.

2 Department of Mathematics, Christ University, Bangalore, India.

Abstract

The chromatic number, χ(G) of a graph G is the minimum number of colours used in a proper colouring of G. In an improper colouring, an edge uv is bad if the colours assigned to the end vertices of the edge is the same. Now, if the available colours are less than that of the chromatic number of graph G, then colouring the graph with the available colours lead to bad edges in G. The number of bad edges resulting from a δ(k)-colouring of G is denoted by bk(G).    In this paper, we use the concept of δ(k)-colouring and determine the number of bad edges in Cartesian product of some graphs.

Keywords

Main Subjects

References

[1] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, New York, 2008.
[2] G. Chartrand and P. Zhang, Chromatic Graph Theory, Chapman and Hall/CRC Press, 2008.
[3] R. Hammack, W. Imrich, and S. Klavžar, Handbook of Product Graphs, CRC Press, 2011.
[4] F. Harary, Graph Theory, Narosa Publ. House, New Delhi., 2001. 
[5] W. Imrich and S. Klavzar, Product Graphs: Structure and Recognition, Wiley, 2000.
[6] T.R. Jensen and B. Toft, Graph Coloring Problems, John Wiley & Sons, 2011.
[7] J. Kok and E.G. Mphako-Banda, Chromatic completion number, J. Math. Comput. Sci. 10 (2020), no. 6, 2971–2983.
[8] J. Kok and S. Naduvath, δ(k)-colouring of cycle related graphs, Adv. Stud. Contemp. Math., to appear.
[9] M. Kubale, Graph Colorings, American Mathematical Soc., 2004.
[10] E.G. Mphako-Banda, An introduction to the k-defect polynomials, Quaest. Math. 42 (2019), no. 2, 207–216.
[11] D.B. West, Introduction to Graph Theory, Prentice hall Upper Saddle River, 2001.
 
Communications in Combinatorics and Optimization
Volume 7, Issue 1
June 2022
Pages 113-120

Files

Share

How to cite

Statistics