Affordable Access

Publisher Website

The cochromatic index of a graph

Discrete Mathematics
Publication Date
DOI: 10.1016/0012-365x(80)90031-x


Abstract We discuss partitions of the edge set of a graph into subsets which are uniform in their internal relationships; i.e., the edges are independent, they are incident with a common vertex (a star), or three edges meet in a triangle. We define the cochromatic index z′( G) of G to be the minimum number of subsets into which the edge set of G can be partitioned so that the edges in any subset are either mutually adjacent or independent. Several bounds for z′( G) are discussed. For example, it is shown that δ( G) - 1 ⩽ z′( G)⩽ Δ( G) + 1, with the lower bound being attained only for a complete graph. Here δ( G) and Δ( G) denote the minimum and maximum degrees of G, respectively. The cochromatic index is also found for complete n-partite graphs. Given a graph G define a sequence of graphs G 0, G 1,…, G k, with G 0= G and G i+1=G i -{;υ | deg G i υ = Δ(G i)} , with k being the first value of i for which G i is regular. Let φ i ( G) = | V( G) – V( G i | + Δ ( G i ) and set φ( G) = min 0⩽ i⩽ k φ i ( G). We show that φ( G) − 1 ⩽ z′( G)⩽ φ( G) + 1. We then s that a graph G is of class A, B or C, if z′( G) = φ( G) − 1, φ( G), or φ( G) + 1, respectively. Examples of graphs of each class are presented; in particular, it is shown that any bipartite graph belongs to class B. Finally, we show that if a, b and c are positive integers with a⩽ b⩽ c + 1 and a⩽ c, then unless a = c = b - 1 = 1, there exists a graph G having δ( G) = a, Δ( G) = c, and z′( G) = b.

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times

More articles like this

On indexable graphs

on Discrete Mathematics Jan 01, 1996
More articles like this..