臺灣大學數學系演講公告 博士生論文口試

Speaker：徐祥峻

Title：Partition Problems of Graphs

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 notations in graph theory. We study the first-fit partitions and the first-fit chromatic number of graphs in chapter 2. We give an upper bound for any family of graphs which is closed under taking induced subgraphs and satisfies $e(G) \le d \cdot n(G)$ for any graph $G$ in this family, where $d$ is an arbitrary positive real number. A vertex-weighted graph $G$ 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$, which attempts to partition $V(G)$ into indepedent sets such that the sum of the maximum weight in each independent set is minimum. We give an upper bound for the number of sets needed in an optimal vertex partition of any vertex-weighted $r$-partite graph. We then extend the Nordhaus-Gaddum inequality to vertex-weighted graphs. We also consider the properties of the perfection on vertex-weighted graphs. The balanced decomposition number of a graph $G$ is the minimum number of the maximum size of a set in an $(R,B)$-balanced decomposition for any balanced coloring $\{R,B,U\}$ of $G$. In chapter 4, we give another proof of that a graph $G$ has balanced decomposition number $3$ if and only if $G$ is $\lfloor\frac{n(G)}{2}\rfloor$-connected and $G$ is not a complete graph. We then extend the definition of a balanced coloring using $k$ colors, and call the corresponding parameter the balanced $k$-decomposition number. We compute the balanced $k$-decomposition number of trees and complete multipartite graphs. 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 \le m \le n$ and $n \equiv 0,-1,-2$ {\rm (mod} $2^{\lceil\log_2 m\rceil})$, the parity and strong parity edge-chromatic number of the complete bipartite graph $K_{m,n}$ is $m \circ n$, the Hopf-Stiefel function. We also consider the parity and strong parity edge-chromatic number of the products of graphs.

Time：13:30~15:30, June. 08(Fri.), 2012

Place：Room 526, Astronomy and Mathematics Building, National Taiwan University(臺灣大學天文數學館526室)