Oriented Coloring Of Some Graphs

An oriented graph is an orientation of an undirected graph, obtained by assign-ing to every edge one of the two possible orientations. Oriented graphs considered in the paper are simple graphs, which are directed graphs without opposite arcs. For an oriented graph, we use V(G), A(G),δ(G),Δ(G), d(v) to denote the vertex set, the arc set.the minimum(vertex)degree, the maximum degree, the degree of v. If u,u are two adjacent vertices in G, we use uu to denote arc from u to u. The order of G is the number of vertices in G.Let G and H be either two graphs or two digraphs. A homomorphism of G to H is a mapping f:V(G)→V(H) that preserves the edges or the arcs: (x,y)∈6 E(G)(?)(ψ(x),ψ(y))∈E(H). The existence (resp. non-existence) of such a homomorphism is denoted by G→H (resp. G→H).A (proper)κ-coloring of a graph H is a partition of V(H) into k subsets, called color classes, such that no two adjacent vertices belong to the same color class. Such aκ-coloring can be equivalently regarded as a homomorphism of H to the complete graph Kk onκ-vertices. Therefore, the chromatic numberχ(H) of a graph H, defined as the smallest k such that H admits aκ-coloring, corresponds to the smallest k such that H→Kκand H→Kκ-1.An orientation of a graph G is a digraph obtained from G by giving to every edge one of its two possible orientations. A digraph G is an oriented graph if it is an orientation of some graph G. As before, homomorphisms of oriented graphs induce the notion of oriented graph coloring as follows. An orientedκ-coloring of an oriented graph G is a partition of V(G) into k color classes such that:(i) no two adjacent vertices belong to the same color class and (ii) all the arcs linking two color classes have the same direction. We can then define the oriented chromatic number of an oriented graph G, denoted by xo(H), as the smallest k such that G has an orientedκ-coloring or, equivalently, as the minimum order of an oriented graph H such that G→H. This notion can be extended to graphs as follows:the oriented chromatic number of a graph is defined as the maximum of the oriented chromatic numbers of its orientations. A strong oriented coloring is a oriented coloring, but its homomorphism is Caley graph. Strong chromatic number is defined as Xs(H).For oriented coloring, Kostochka and Sopena proved that families of graphs with bounded acyclic chromatic number have also bounded oriented chromatic number. Robert Samal considered the strong oriented coloring of planar graphs. Ochem proved the oriented coloring of triangle-free planar graphs. Borodin considered the relationship between girth and oriented coloring number.In the paper, we consider oriented coloring of some degenerate graphs, and strong oriented coloring of of double-outer planar graphs and special planar graphs, and obtain the following theorems.Theorem 1 If G is a 2-degenerate graph, then Xs(G)≤7.Theorem 2 If G is a 3-degenerate graph, then Xs(G)≤19.Theorem 3 If G is a 4-degenerate graph, then Xs(G)≤67.Theorem 4 If G is a double-outer planar graph, and is not isomorphism to P, then Xs(G)≤19, X,(P)≤67Theorem 5 Let G be a planar graph without cycles of lengthes 4 to 7, then Xs(G)≤19.Finally, we generalize the definition of oriented coloring, and give a new coloring-2-dipath coloring.Let m≥1 be an integer. A m-dipathκ-coloring f of an oriented graph G is a mapping from V(G) to the color set{1,2,..., k} such that:(i) f(x)≠f(y) for any two vertices x and y with 1≤d(x,y)≤m; (ii) all the arcs linking two color classes have the same direction. The m-dipath chromatic number, denoted byχm(G), of an oriented graph G is the smallest k such that G has a m-dipathκ-coloring. The m-dipath chromatic numberχm(G) of an undirected graph G is defined as the maximum of m-dipath chromatic number of its orientations. Ifm=2, thenχm(G) is the 2-dipath chromatic number of a graph G.According to the 2-dipath chromatic number of Halin graphs, we give a conjec-ture about 2-dipath chromatic number of 2-degenerate graphs.Conjecture If G is a 2-degenerate graph, thenχm(G)≤5.