Title: The b-chromatic number of Mycielskian of some graphs

Authors: P.C. Lisna; M.S. Sunitha

Addresses: Department of Mathematics, National Institute of Technology Calicut, Kozhikode – 673 601, India ' Department of Mathematics, National Institute of Technology Calicut, Kozhikode – 673 601, India

Abstract: A b-colouring of a graph G is a proper colouring of the vertices of G such that there exists a vertex in each colour class joined to at least one vertex in each other colour classes. The b-chromatic number of a graph G, denoted by φ(G) is the largest integer k such that G has a b-colouring with k colours. The Mycielskian or Mycielski graph µ(H) of a graph H with vertex set {v₁, v₂, , v_n} is a graph G obtained from H by adding n + 1 new vertices {u, u₁, u₂, , u_n}, joining u to each vertex u_i (1 ≤ i ≤ n) and joining u_i to each neighbour of v_i in H. In this paper, we obtain the b-chromatic number of Mycielskian of paths, complete graphs, complete bipartite graphs and wheels.

Keywords: b-chromatic number; b-colouring; b-dominating set; Mycielskian; graphs; Mycielski graph.

DOI: 10.1504/IJCONVC.2016.080395

International Journal of Convergence Computing, 2016 Vol.2 No.1, pp.23 - 40

Received: 30 Apr 2015
Accepted: 16 Jun 2016
Published online: 21 Nov 2016 *