Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Diameter Of 3-Colorable Graphs And Some Remarks On The Midrange Crossing Constant, Inne Singgih
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 Kk.
Let r, δ ≥ 2 be fixed integers and let G be a connected graph with n vertices …