Affordable Access

Publisher Website

The cochromatic index of a graph

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
31
Issue
2
Identifiers
DOI: 10.1016/0012-365x(80)90031-x

Abstract

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.

Statistics

Seen <100 times
0 Comments

More articles like this

b-chromatic index of graphs

on Electronic Notes in Discrete M... Nov 05, 2013

The PI index of product graphs

on Applied Mathematics Letters Jan 01, 2008
More articles like this..