(0,1)-Matrices without any half-half all 1's submatrix, and, Connectivity ofk-chromatic graphs

his thesis consists two separate topics. Chapter One is joint work with Professor J. Griggs on (0,1)-matrix without half-half submatrix being all 1's. Let f(m, n) be the least number of 0's in any 2m ;In Chapter Two we solve a conjecture about the connectivity of k-chromatic graph. Given a positive integer k, Chen, Schelp and Shreve ask for the smallest number f(k) such that for any connected k-chromatic graph G there exists a k-coloring of V(G) with color classes...