Date of Award
Open Access Dissertation
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 and minimum degree δ. In general, Erdős et al. conjectured tight upper bounds for K2r -free and K2r+1-free graphs that are better than the known δ+1 + O(1). Particular to this dissertation, their conjecture stated that K5-free graphs with 5 l δ have diameter ≤ 2δ + O(1), while K4-free graphs with 8 l δ have diameter ≤ 7δ + O(1).
The first progress towards this conjecture was published by Czabarka, Dankel- mann, and Székely in 2008. They worked under the stronger assumption for when r = 2, that the graphs are 4-colorable rather than K5-free. They showed that for every connected 4-colorable graph G of order n and δ ≥ 1, diam(G) ≤ 5n − 1.
We provide a counterexample to this 30 years old unsolved conjecture for K4-free graphs by showing classes of 3-colorable graphs with diameter 7n 3δ+3+ O(1). From here we conjectured that 3-colorable graphs has diameter at most 7n + O(1). We use the Duality of Linear Programming to prove 3-colorable graphs have diameter at most 2δ + O(1). We then utilize inclusion-exclusion into a different linear programming approach to prove a smaller upper bound that for every connected 3-colorable graph G of order n and δ ≥ 1, diam(G) ≤ 189n + O (1).
The second part of this dissertation gives some remarks on the midrange crossing constant. The celebrated Crossing Lemma states that for any graph on n vertices and m C 4n edges we have cr(G) n2 m3 is at least 1 64 . A decade before the Crossing Lemma, Erdos and Guy made the bold conjecture that, if we denote by k(n,m) the minimum crossing number of n-vertex graph with at least m = m(n) edges, then there is a positive constant , dubbed as the midrange crossing constant, such that = lim n ∞ ª k(n,m) n2 m3 as long as m is both superlinear in n. Pach, Spencer and Tóth showed that the Erdos-Guy conjecture is true with the additional (and needed) assumption that m is subquadratic. Pach, Radoicic, Tardos and Tóth gave a construction yielding B 8 9 ϖ 2 ≈0.0900633 for the rectilinear midrange crossing constant. Details of neither of these calculations, which are said to be long and unpleasant, are available to the public. We provide a simple alternative construction that yields the same upper bound.
Singgih, I.(2020). Diameter of 3-Colorable Graphs and Some Remarks on the Midrange Crossing Constant. (Doctoral dissertation). Retrieved from https://scholarcommons.sc.edu/etd/5678