Physical Sciences and Mathematics Commons^™

Diameter Of 3-Colorable Graphs And Some Remarks On The Midrange Crossing Constant, Inne Singgih

Theses and Dissertations

The first part of this dissertation discussing the problem of bounding the diameter of a graph in terms of its order and minimum degree. The initial problem was solved independently by several authors between 1965 − 1989. They proved that for fixed δ ≥ 2 and large n, diam(G) ≤ 3n+ O(1). In 1989, Erdős, Pach, Pollack, and Tuza conjectured that the upper bound on the diameter can be improved if G does not contain a large complete subgraph K_k.

Let r, δ ≥ 2 be fixed integers and let G be a connected graph with n vertices …