Strong Edge Coloring of Outerplane Graphs with Independent Crossings

The strong chromatic index of a graph is the minimum number of colors needed in a proper edge coloring so that no edge is adjacent to two edges of the same color.An outerplane graph with independent crossings is a graph embedded in the plane in such a way that all vertices are on the outer face and two pairs of crossing edges share no common end vertex.It is proved that every outerplane graph with independent crossings and maximum degreeΔhas strong chromatic index at most 4Δ-6 if Δ≥4,and at most 8 ifΔ≤3.Both bounds are sharp.

On the adjacent vertex-distinguishing acyclic edge coloring of some graphs

A proper edge coloring of a graph G is called adjacent vertex-distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the coloring set of edges incident with u is not equal to the coloring set of edges incident with v, where uv∈ E（G）. The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by X＇Aa（G）, is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. If a graph G has an adjacent vertex distinguishing acyclic edge coloring, then G is called adjacent vertex distinguishing acyclic. In this paper, we obtain adjacent vertex-distinguishing acyclic edge coloring of some graphs and put forward some conjectures.

On the Adjacent Strong Edge Coloring of Outer Plane Graphs

A k-adjacent strong edge coloring of graph G(V, E) is defined as a proper k-edge coloring f of graph G(V, E) such that f[u] ≠ f[v] for every uv ∈ E(G), where f[u] = {f(uw)|uw ∈ E(G)} and f(uw) denotes the color of uw, and the adjacent strong edge chromatic number is defined as x'as(G) = min{k| there is a k-adjacent strong edge coloring of G}. In this paper, it has been proved that △ ≤ x'as(G) ≤ △ + 1 for outer plane graphs with △(G) ≥ 5, and X'as(G) = △ + 1 if and only if there exist adjacent vertices with maximum degree.

On the Adjacent Strong Edge Coloring of Halin Graphs

A proper k-edge coloring f of graph G(V, E) is said to be a k:-adjacent strong edge coloring of graph G(V,E) iff every uv∈E(G) satisfy f[u]≠f/[v], where f[u] = {f(uw)|uw ∈E(G)} then f is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC: and x'as(G) = min{k|k-ASEC of G} is called the adjacent strong edge chromatic number. In this paper, we study the x'as(G) of Halin graphs with △A(G)≥5.

On the Vertex Strong Total Coloring of Halin-Graphs

A proper k-total coloring f of the graph G（V, E） is said to be a k-vertex strong total coloring if and only if for every v ∈ V（G）, the elements in N[v] are colored with different colors, where N[v] =. {u｜uv E V（G）} ∪{v}. The value xT^vs（G） = min{k｜ there is a k-vertex strong total coloring of G} is called the vertex strong total chromatic number of G. For a 3-connected plane graph G（V, E）, if the graph obtained from G（V, E） by deleting all the edges on the boundary of a face f0 is a tree, then G（V, E） is called a Halin-graph. In this paper, xT^vs,8（G） of the Halin-graph G（V,E） with A（G） 〉 6 and some special graphs are obtained. Furthermore, a conjecture is initialized as follows： Let G（V, E） be a graph with the order of each component are at least 6, then xT^vs（G） ≤ △（G） ＋ 2, where A（G） is the maximum degree of G.

A Note on Adjacent Strong Edge Coloring of K(n,m)

In this paper, we prove that the adjacent strong edge chromatic number of a graph K（n,m） is n ＋ 1, with n ≥ 2, m ≥ 1.

Adjacent strong edge colorings and total colorings of regular graphs

It is conjectured that X as ′ (G) = X t (G) for every k-regular graph G with no C 5 component (k ? 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V(G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.

Adjacent Strong Edge Chromatic Number of Series-Parallel Graphs

In this paper, we will study the adjacent strong edge coloring of series-parallel graphs, and prove that series-parallel graphs of △(G) = 3 and 4 satisfy the conjecture of adjacent strong edge coloring using the double inductions and the method of exchanging colors from the aspect of configuration property. For series-parallel graphs of △(G) ≥ 5, △(G) ≤ x'as(G) ≤ △(G) + 1. Moreover, x'as(G) = △(G) + 1 if and only if it has two adjacent vertices of maximum degree, where △(G) and X'as(G) denote the maximum degree and the adjacent strong edge chromatic number of graph G respectively.

An Upper Bound for the Adjacent Vertex Distinguishing Acyclic Edge Chromatic Number of a Graph

A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges incident to v, where uv ∈E（G）. The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by χ＇αα（G）, is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. In this paper we prove that if G（V, E） is a graph with no isolated edges, then χ＇αα（G）≤32△.