Semester
Spring
Date of Graduation
2019
Document Type
Dissertation
Degree Type
PhD
College
Eberly College of Arts and Sciences
Department
Mathematics
Committee Chair
Rong Luo
Committee Co-Chair
John Goldwasser
Committee Member
John Goldwasser
Committee Member
Hong-Jian Lai
Committee Member
Cun-Quan Zhang
Committee Member
Yue Zhao
Abstract
In my dissertation, I present results on two types of edge coloring problems for graphs.
For each surface Σ, we define ∆(Σ) = max{∆(G)| G is a class two graph with maximum degree ∆(G) that can be embedded in Σ}. Hence Vizing’s Planar Graph Conjecture can be restated as ∆(Σ) = 5 if Σ is a sphere. For a surface Σ with characteristic χ(Σ) ≤ 0, it is known ∆(Σ) ≥ H(χ(Σ))−1, where H(χ(Σ)) is the Heawood number of the surface, and if the Euler char- acteristic χ(Σ) ∈ {−7, −6, . . . , −1, 0}, ∆(Σ) is already known. I study critical graphs on general surfaces and show that (1) if G is a critical graph embeddable on a surface Σ with Euler character- istic χ(Σ) ∈ {−6, −7}, then ∆(Σ) = 10, and (2) if G is a critical graph embeddable on a surface Σ with Euler characteristic χ(Σ) ≤ −8, then ∆(G) ≤ H(χ(Σ)) (or H(χ(Σ))+1) for some special families of graphs, namely if the minimum degree is at most 11 or if ∆ is very large et al. As applications, we show that ∆(Σ) ≤ H (χ(Σ)) if χ(Σ) ∈ {−22, −21, −20, −18, −17, −15, . . . , −8}and ∆(Σ) ≤ H (χ(Σ)) + 1 if χ(Σ) ∈ {−53, . . . , 23, −19, −16}. Combining this with [19], it follows that if χ(Σ) = −12 and Σ is orientable, then ∆(Σ) = H(χ(Σ)).
A star k-edge-coloring is a proper k-edge-coloring such that every connected bicolored sub-
graph is a path of length at most 3. The star chromatic index χ′st(G) of a graph G is the smallest
integer k such that G has a star k-edge-coloring. The list star chromatic index ch′st(G) is defined
analogously. Bezegova et al. and Deng et al. independently proved that χ′ (T) ≤ 3∆ for anyst 2
tree T with maximum degree ∆. Here, we study the list star edge coloring and give tree-like
bounds for (list) star chromatic index of sparse graphs. We show that if mad(G) < 2.4, then
χ′ (G)≤3∆+2andifmad(G)<15,thench′ (G)≤3∆+1.Wealsoshowthatforeveryε>0st 2 7 st 2
there exists a constant c(ε) such that if mad(G) < 8 − ε, then ch′ (G) ≤ 3∆ + c(ε). We also3 st 2
find guaranteed substructures of graph with mad(G) < 3∆ − ε which may be of interest in other2
problems for sparse graphs.
Recommended Citation
Horacek, Katherine M., "Edge colorings of graphs on surfaces and star edge colorings of sparse graphs" (2019). Graduate Theses, Dissertations, and Problem Reports. 3910.
https://researchrepository.wvu.edu/etd/3910