圖的四類分解問題之研究

Abstract

Partition problems of graphs are optimization problems about partitions of the vertex set V(G) or the edge set E(G) of a graph G under some additional restrictions. We begin this thesis by introducing some partition problems, basic definitions and notation in graph theory. We study first-fit partitions and the first-fit chromatic numbers of graphs in Chapter 2. Given a family F of graphs satisfying that F is closed under taking induced subgraphs and e(G) ≤ dn(G) for any graph G ∈ F, where d is an arbitrary positive real number, we give an upper bound for the first-fit chromatic number of any graph in F. This result applies to d-degenerate graphs, planar graphs, and outerplanar graphs. A vertex-weighted graph (G,c) is a graph G with a positive weight c(v) on each vertex v in G. In Chapter 3, we study the max-coloring problem of a vertex-weighted graph (G,c), which attempts to partition V(G) into independent sets such that the sum of the maximum weight in each independent set is minimum. This is a weighted version of the usual vertex coloring problem of a graph. We give an upper bound for the number of sets needed in an optimal vertex partition of a vertex-weighted r-partite graph. We then derive the Nordhaus-Gaddum inequality for vertex-weighted graphs. We also consider the properties of the perfection on vertex-weighted graphs. A balanced coloring of a graph G is a partition {R,B,U} of V (G) with |R| = |B|, where R,B and U stand for the sets of red, blue and uncolored vertices in G, respectively. For a graph G with a balanced coloring {R,B,U}, an (R,B)-balanced decomposition is a partition P of V(G) such that the induced subgraph G[S] is connected and |S ∩ R| = |S ∩ B| for any S in P. The balanced decomposition number f(G) of a graph G is the minimum integer l such that for any balanced coloring (R,B) of G there is an (R,B)-balanced decomposition P with |S| ≤ l for S ∈ P. In Chapter 4, we give a shorter proof of a known result that a graph G has balanced decomposition number 3 if and only if G is [n(G)/2]-connected and G is not a complete graph. We then extend the definition of a balanced coloring using two colors to k colors, and call the corresponding parameter the balanced k-decomposition number. We compute the balanced k-decomposition numbers of trees and complete multipartite graphs. A parity edge-coloring of a graph G is an edge-coloring of G such that any path of positive length uses some color an odd number of times. A strong parity edge-coloring of a graph G is an edge-coloring of G such that any open walk uses some color an odd number of times. The parity (strong parity) edge-chromatic number of a graph G is the minimum number of colors used in a parity (strong parity) edge-coloring of G. In Chapter 5, we prove that, for 3 ≤ m ≤ n and n ≡ 0,−1,−2 (mod 2^{lceil lg m rceil}), the (strong) parity edge-chromatic number of the complete bipartite graph K_{m,n} is m◦n, the Hopf-Stiefel function, which is the least integer l such that C(l,k) is even for each k with l − n < k < m. We also consider the parity and the strong parity edge-chromatic numbers of the products of graphs.