Edge-face Coloring And Entire Coloring Of Plane Graphs

An edge-face (or an entire) κ-coloring of a plane graph G is a mapping φ:E(G) U F(G)â†'1,2,…,k}(or φp:V(G)UE(G)UF(G)â†'{1,2,…,κ}), such that φ(y) for each pair of adjacent or incident elements x,y∈E(G)UF(G)(or x,y∈V(G)∪E(G)∪F(G)). The edge-face chromatic number χef/(G)(or entire chromatic number χvef(G)), is the least non-negative integer κ such that G has an edge-face (or entire) κ-coloring.If G has an edge-face coloring Ï€, such that Ï€(x)∈L(x) for each x∈E(G)∪F(G), then we say that G is edge-face L-colorable. If, for any list L satisfying|L(x)|≥fc for each x∈E(G)∪F(G), G is edge-face L-colorable, then G is called edge-face κ-choosable. The list edge-face chromatic number chef(G) is the least non-negative integer κ such that G has an edge-face κ-choosable. Similarly, we can define list entire coloring, and use chvef(G) to denote list entire chromatic number.The edge-face coloring of plane graphs was first considered by Jucovic(1969) and Fiamchik(1971). Borodin proved that ifâ–³(G)≥10, then χef(G)≤△(G)+1, which can be extended to the list edge-face coloring version. Wang and Lih asked for a sharp upper bound for chef(G) when G is a plane graph with3≤△(G)≤9.The entire coloring of a plane graph was introduced by Ringel(1965). In1993, Borodin proved that if G is a plane graph withâ–³(G)≥12, then χvef(G)≤△(G)+2. Also he proposed a question:what is the tight upper bound about χvef(G) for plane graphs G withâ–³(G)≤11? Moreover, Borodin confirmed that if G is a plane graph with A(G)≥7, then chvef(G)≤△(G)+4. Dong Wei proved that if G is a plane graph withâ–³(G)≥, then chvef(G)≤△(G)+5.In this master thesis, we study the edge-face list coloring and entire coloring of plane graphs. The thesis consists of four chapters.In Chapter1, we collect some basic notations, give a chief survey in this direction and state the main results obtained.In Chapter2, we study the entire coloring of plane graphs by showing that any plane graph G withâ–³(G)≥9is entirely (â–³(G)+2)-colorable.In Chapter3, we study the list entire coloring of plane graphs and obtain the following two results:(1)Any plane graph G withâ–³(G)≤5is entirely(â–³(G)+5)-choosable.(2)Any’plane graph G withâ–³(G)≥10is entirely(â–³(G)+2)-choosable.In Chapter4,we study the list edge-face coloring of plane graphs and prove that any plane graph G withâ–³(G)≥9is edge-face(â–³(G)+2)-choosable.