Figure 2. Binary Staining Number Study

Let G be a simple graph.An independent set of G is a subset of V(G)that does not contain two adjacent vertices.A clique of G is a set of pairwise adjacent vertices.The maximum order over all cliques of G is called the clique number of G and is denoted by ?(G).A(k,l)-coloring of G is a partition of its vertex set into k independent sets and l cliques.We say that G is(k,l)-colorable if there exists a(k,l)-coloring of G.The cochromatic number Xc(G)of G is the minimum r such that G is(k,l)-colorable for some nonnegative integers k and l with k|l=r.The bichrornatic number ?b(G)of G is the minimum r such that G is(k,l)-colorable for all nonnegative integers k and l with k+l=r.An l-clique-covering of G is a partition C1,C2,...,Cl of V(G)such that each Cj is a clique.A graph G is lclique-coverable if it has an l-clique-covering.The minimum number l,for which G is l-clique-coverable is the clique covering number of G and is denoted by ?(G).A main focus of this thesis is on(k,l)-colorings of some graph classes.For any graph G with ?(G)<r,r=3 or 4,we find the upper bound for the bichromatic number is ?b(G)??(G)+r-2,where ?(G)is the clique number and ?(G)the clique covering number of G.If r>4,likewise,we have the upper bound ?b(G)??(G)|r-2 for the line graphs G with ?(G)<r.Also,We characterize all the extremal graphs.