On ?(k)-coloring of graph products

Title

On ?(k)-coloring of graph products

Creator

Ellumkalayil M.T.; Naduvath S.

Description

An edge which is incident on two vertices that are assigned the same color is called a bad edge. A near proper coloring is a coloring that minimises the number of bad edges in a graph G, by permitting few color classes to have adjacency between the elements in it. A near proper coloring, that uses k colors where 1 ? k ? ?(G) ? 1, which allows at most one color class to be a non independent set to minimise the number of bad edges resulting from the same is called a ?(k)-coloring. In this paper, we determine the minimum number of bad edges, bk(G), resulting from a ?(k)- coloring of some graph products viz. direct product of two graphs G H and corona product of two graphs G?H, for all different possible values of k by investigating an optimal ?(k)-coloring that results in minimum number of bad edges. (2023), (Institute of Combinatorics and its Applications). All Rights Reserved.

Source

Bulletin of the Institute of Combinatorics and its Applications, Vol-99, pp. 58-90.

Date

2023-01-01

Publisher

Institute of Combinatorics and its Applications

Subject

bad edges; Improper coloring; near proper coloring; ?^(k)-coloring

Coverage

Ellumkalayil M.T., DEPARTMENT OF MATHEMATICS, CHRIST (DEEMED TO BE UNIVERSITY), Karnataka, Bangalore, 560029, India; Naduvath S., DEPARTMENT OF MATHEMATICS, CHRIST (DEEMED TO BE UNIVERSITY), Karnataka, Bangalore, 560029, India

Rights

Restricted Access

Relation

ISSN: 11831278

Format

Online

Language

English

Type

Article

Identifier

https://www.scopus.com/inward/record.uri?eid=2-s2.0-85178479205&partnerID=40&md5=e765e1b1614017060239ee18e6d9eb97