On Some Generalized Colorings For Graphs

The study on graph colorings plays a central role in graph theory. Coloring problem is indeed a kind of partition problem, and each color class corresponds to one part of the partition. In classical coloring theory, we color the vertices (resp. edges) of a graph requiring only that no two adjacent vertices (resp. edges) receive the same color. Here we consider generalized colorings which have both weakenings and strengthenings of those requirements. Roughly speaking, the problems that we are concerned in this thesis can be divided into the following four parts:1. Induced matching partition number.2. Vertex arboricity.3. Near-bipartition.4. Adjacent strong edge chromatic number.Induced matching partition numberA matching in a graph G is a set of edges no two of which are adjacent. If each vertex v of G is incident with one edge of a matching M, then M is called a perfect matching and if no two edges of a matching M are joined by an edge, then M is called an induced matching. An induced matching fc-partition of a graph G having perfect matchings is a fc-partition (coloring) (V1, V2, ...,Vfc) of V(G) such that, for each i (1 < i < fc), E(Vi) is an induced matching of G that covers Vi, or equivalently, G[Vi] is 1-regular. The induced matching partition number of a graph G, denoted by imp(G), is the minimum positive integer fc such that G has an induced matching fc-partition. Historically, the induced matching fc-partition problem was first researched as a combinatorial optimization problem [16]. By [16, 36], the induced matching fc-partition problem is NP-complete, and also NP-complete for k = 2 and for 3-regular planar graphs, respectively. Yuan and Wang [44] showed that, for a graph G having perfect matchings, imp(G) < 2A(G) - 1; the equality holds if and only if G is isomorphic to one of K2, C4k+2 and the Petersen graph. We study the computational complexity of this problem for graphs of small diameter and derive exact results for some special graphs.Theorem 1. The induced matching 2-partition problem for graphs having diameter 6 is NP-complete.Theorem 2. The induced matching 3-partition problem for graphs having diameter 2 is NP-complete.Theorem 3. Let G be a graph of diameter 2. SetE0 = {xy E(G) : each component of G[N({x,y})] is isomorphic to K1 or K2}.Then imp(G) = 2 if and only if one of the following two conditions holds:(1) There exists an E' C E(G) such that 1 < |E'| < 2, and both G[N(V(E'))] and G - N(V(E')) are 1-regular.(2) E0 is a perfect matching of G and G E0 is a bipartite graph.Based on Theorem 3, we obtain a polynomial time algorithm to solve the induced matching 2-partition problem for graphs of diameter 2. Next we give a more simple characterization for the induced matching 2-partition problem for planar graphs of diameter 2.Theorem 4. Let G be a planar graph of diameter 2. Then imp(G) = 2 if and only if there exists an xy G E{G) such that both G[N({x, y})] and G - N({x, y}) are 1-regular.Theorem 5. Let G and H be two graphs. Then where x{G) stands for the chromatic number of G.Theorem 6. Let G and H be two graphs such that G has perfect matchings. Thenimp(G xH)< max{imp(G),x(H)}.The bounds in Theorems 5 and 6 are best possible and many tight examples are illustrated in the paper.Theorem 7. imp(G K2) = x{G).The A;-trees can be recursively defined below: (a) Kk+1 is a k-tree; (6) a k-tree G of n + 1 vertices can be obtained from a fc-tree G' of n vertices by joining a new vertex to all vertices of a Kk in G'. The treewidth [33, 34] of a graph G, denoted by TW(G), is the minimum integer k that G is a subgraph of a k-tree.Theorem 8. For a graph G, imp(G) < TW(G) + 1.Corollary 9. For a connected chordal graph G, imp(G) < (G).Theorem 10. Let G be a 2-tree with at least four vertices. Then imp{G) = 2 if and only if it is isomorphic to a ladder-tree.Corollary 11. Let G be a maximal outerplanar graph with at least four vertices. Then imp(G) - 2 if and only if it is isomorphic to a ladder-path.Theorem 12. Let G be a maximal pl...