Colorings Of Graphs Embedded In Surfaces Of Nonnegative Euler Characteristic

Coloring of graphs is an important branch of graph theory. In our paper we mainly make some research on total coloring of graphs and linear arboricity of graphs.A total k-coloring of a graph G is a coloring of V U E using κ colors such that no two adjacent or incident elements receive the same color. The total chromatic number of G is the smallest integer k such that G has a total κ-coloring. Clearly, x"(G)≥Δ(G)+1. Behzad and Vizing independently came out with the following conjeeture(TCC): Conjecture1For any graph G, Δ(G)+1≤x"(G)≤Δ(G)+2.This conjecture was verified by Rosenfeld and Vijayadiya for Δ(G)=3and by Kostochka for Δ(G)≤5. For planar graphs, more results were obtained. Borodin proved TCC for planar graphs with Δ(G)≥9. By applying the Four Color Theorem, this result was extended to Δ(G)≥8. In1999, Sanders and Zhao strengthened it to Δ(G)>≥7. So the only case of TCC for planar graphs that remained open was only Δ(G)=6. But when we add some restrictions of girth or cycles, there are a lot results when Δ(G)=6.Surfaces in our paper are compact, connected two manifolds without boundary. All embeddings considered in our paper are2-cell embeddings. Let G be a graph embedded in a surface Σ of Euler characteristic x(Σ)≥0. Zhao proved TCC for G with Δ(G)≥8. Wang and Liu strengthened it to Δ≥7.In the second section of our paper, we proved several results:Let G be a graph embedded in a surface Σ of Euler characteristic x(Σ)≥0, then(1) Δ(G)=6, Ghas no intersecting3-cycle or intersecting4-cycle, then x’(G)=Δ(G)+1. (2) Δ(G)=7, Ghas no4-cycle, x"(G)-Δ(G)+1.(3) Δ(G)≥6, G has no5-cycle or incident4-cycle, then x"(G)<Δ(G)+2.A linear forest is a graph in which each component is a path. A map? from E(G) to {1,2,???, t} is called a t-linear coloring if (V (G),?-1(α)) is a linear forest for1≤α≤t. The linear arboricity la(G) of a graph G defined by Harary is the minimum number t for which G has a t-linear coloring.There is a famous conjecture for the linear arboricity: Conjecture2For any graph G,[2Δ(G)]≤la(G)≤[2Δ(G)+1]Peroche proved that the determination of the linear arboricity of a graph G is an NP-hard problem, even when Δ(G)=4. For planar graphs, LAC is proved by Wu. And they got a conclusion that for a planar graph with Δ(G)≥9, la(G)=[2Δ(G)].Wang proved that LAC is correct for a graph embedded in a surface E of Euler characteristic x(Σ)>0, and la(G)=[2Δ(G)] for Δ(G)≥9.In the third section of our paper, we proved several results about the linear arboricity:Let G be a graph embedded in a surface Σ of Euler characteristic x(Σ)≥0, suppose that dis an integer with d≥4and Δ(G)≤2d, when:(1) Δ(G)≥7, G has no4-cycle, or(2) Δ(G)=7, Ghas no5-cycle,G has a d-linear coloring.