Search ETDs:
On The Coloring of Graphs
Kurt, Oguz

2009, Doctor of Philosophy, Ohio State University, Mathematics.

In this thesis, we consider the problem posed by Gupta, Goldberg and Seymour: “When is the chromatic index χ′ of a graph almost the same as its fractional chromatic index χ*?”. While they conjectured that the answer is when “the chromatic index is at least 2 more than the maximum degree of the graph”, so far this problem is wide open.


The first part of this thesis improves the known results to this problem by following the work of Tashkinov and using the VKT-trees introduced by Chen, Yu and Zang.


In the second part, we show that the ideas of fan and path can be generalized to the analogous problem posed by Gupta by replacing the idea of “covering with matchings” with “packing with edge covers”. While we will not present any explicit results such as the one presented in the first part, this part provides some insight into the nature of alternating chains in this new context.


The last part of this thesis will be a tribute to a recent result by Goldberg. Goldberg shows that it is not necessary to use the matching number of a graph while working on Goldberg-Gupta Conjecture. We prove the analogous result for the analogous conjecture.


Prof. Neil Robertson (Advisor)
Prof. John Maharry (Committee Member)
Prof. Stephen Milne (Committee Member)
Prof. Boris G. Pittel (Committee Member)
119 p.

Recommended Citations

Hide/Show APA Citation

Kurt, O. (2009). On The Coloring of Graphs. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Kurt, Oguz. "On The Coloring of Graphs." Electronic Thesis or Dissertation. Ohio State University, 2009. OhioLINK Electronic Theses and Dissertations Center. 25 Sep 2017.

Hide/Show Chicago Citation

Kurt, Oguz "On The Coloring of Graphs." Electronic Thesis or Dissertation. Ohio State University, 2009. https://etd.ohiolink.edu/

Files

osu1262287401.pdf (733.52 KB) View|Download