The cochromatic index of a graph

✍ Scribed by Lowell Beineke; Richard Ringeisen; H.Joseph Straight

• Publisher: Elsevier Science
• Year: 1980
• Tongue: English
• Weight: 684 KB
• Volume: 31
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(80)90031-x

✦ Synopsis

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 S(G) -1 s z'(G) *C A(G)+ 1, with the lower bound being attained only for a complete graph. Here S(G) nnd A(G) denote the minimum and maximum degrees of G, respectively. The cochromatic inciex is also found ffor complete n-partite graphs.

Given a graph G, define a sequence of graphs Go, G1,. . . , Gk, with Go=G arid Gi+l= Gi -{*j 1 degc;, o = A(Gi)), with k being the first value of i for which Gi is regular. Let 4i'G) = 1 V(G) -V(G,)j + A( G,) and set 4(G) = min O~i~k(bi(G). We show that 4(G)-lsz'(G)s+(G)+l. We then say that a graph G is of class A, B or C, if z'(G) = 4(G) -l,&(G), or 4(G) + 1, respectively. Examples of graphs of each class are presented; in particular, it is shown tha! any bipartite graph belongs to class B. Finally, we show that if a, b, and c are positive integers wiih a s b s c + 1 and a s c, then unless a = c = b -I= 1, there exists a graph G having 6(G) = a, A(G) = c, and zr( G) = b.