(0, 1)-matrices without any half-half all 1's submatrix and connectivity of k-chromatic graphs
Jianxin Ouyang · 1994
This 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 $\times$ 2n (0,1)-matrix such that there is no $m \times n$ submatrix consisting only of 1's. We prove that $f(m, n) \geq 2n + m + 1$ for $n\geq m$, and for each m equality holds for all but finitely many n's. 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 $X\sb1, X\sb2,\...,X\sb{k}$ such that $G\sp{f(k)}(X\sb{i})$ is connected for all i. Here we prove f(k) = k for all k.