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, $\chi(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 $\delta^{(k)}$-colouring of $G$ is denoted by $b_{k}(G)$.    In this paper, we use the concept of $\delta^{(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