English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Edge colorings of graphs on surfaces and star edge colorings of sparse graphs Katherine M. Horacek 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, whereH(χ(Σ)) is the Heawood number of the surface, and if the Euler characteristic χ(Σ) ∈ {−7,−6, . . . ,−1, 0}, ∆(Σ) is already known. I study critical graphs on general surfaces and show that (1) ifG is a critical graph embeddable on a surface Σ with Euler characteristic χ(Σ) ∈ {−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 subgraph 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 chst(G) is defined analogously. Bezegova et al. and Deng et al. independently proved that χst(T ) ≤ 3∆ 2 for any 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 χst(G) ≤ 3∆ 2 + 2 and if mad(G) < 15 7 , then ch ′ st(G) ≤ 3∆ 2 + 1. We also show that for every ε > 0 there exists a constant c(ε) such that if mad(G) < 8 3 − ε, then ch ′ st(G) ≤ 3∆ 2 + c(ε). We also find guaranteed substructures of graph with mad(G) < 3∆ 2 − ε which may be of interest in other problems for sparse graphs.