Note on Cyclically Interval Edge Colorings of Simple Cycles

A proper edge t-coloring of a graph G is a coloring of its edges with colors 1, 2,..., t, such that all colors are used, and no two adjacent edges receive the same color. A cyclically interval t-coloring of a graph G is a proper edge t-coloring of G such that for each vertex, either the set of colors used on edges incident to x or the set of colors not used on edges incident to x forms an interval of integers. In this paper, we provide a new proof of the result on the colors in cyclically interval edge colorings of simple cycles which was first proved by Rafayel R. Kamalian in the paper “On a Number of Colors in Cyclically Interval Edge Colorings of Simple Cycles, Open Journal of Discrete Mathematics, 2013, 43-48”.

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.

Smarandachely Adjacent-vertex-distinguishing Proper Edge Coloring ofK4 V Kn

Let f be a proper edge coloring of G using k colors. For each x ∈ V（G）, the set of the colors appearing on the edges incident with x is denoted by Sf（x） or simply S（x） if no confusion arise. If S（u） = S（v） and S（v） S（u） for any two adjacent vertices u and v, then f is called a Smarandachely adjacent vertex distinguishing proper edge col- oring using k colors, or k-SA-edge coloring. The minimum number k for which G has a Smarandachely adjacent-vertex-distinguishing proper edge coloring using k colors is called the Smarandachely adjacent-vertex-distinguishing proper edge chromatic number, or SA- edge chromatic number for short, and denoted by Xsa（G）. In this paper, we have discussed the SA-edge chromatic number of K4 V Kn.

Edge Coloring of Graphs with Applications in Coding Theory

In this paper,a new type of edge coloring of graphs together with an algorithm for such an edge coloring is presented to construct some columnweight three low-density parity-check(LDPC)codes whose Tanner graphs are free of 4-cycles.This kind of edge coloring is applied on some well-known classes of graphs such as complete graphs and complete bipartite graphs to generate some column-weight 3 LDPC codes having flexibility in terms of code length and rate.Interestingly,the constructed(3;k)-regular codes with regularities k=4;5;:::;22 have lengths n=12;20;26,35;48;57;70;88;104;117;140;155;176;204;228;247;280;301;330;having minimum block length compared to the best known similar codes in the literature.In addition to linear complexity of generating such parity-check matrices,they can be considered as the base matrices of some quasi-cyclic(QC)LDPC codes with maximum achievable girth 18,which inherit the low-complexity encoder implementations of QC-LDPC codes.Simulation results show that the QC-LDPC codes with large girth lifted from the constructed base matrices have good performances and outperform random codes,progressive edge growth LDPC codes,some finite fields and group rings based QC-LDPC codes and also have a close competition to the standard IEEE 802.16e(WiMAX)code.

ON EQUITABLE VERTEX DISTINGUISHING EDGE COLORINGS OF TREES

It has been known that determining the exact value of vertex distinguishing edge index X ＇8（G） of a graph G is difficult, even for simple classes of graphs such as paths, cycles, bipartite complete graphs, complete, graphs, and graphs with maximum degree 2. Let rid（G） denote the number of vertices of degree d in G, and let X＇es（G） be the equitable vertex distinguishing edge index of G. We show that a tree T holds nl （T） ≤ X ＇s （T） ≤ n1 （T） ＋ 1 and X＇s（T） = X＇es（T） if T satisfies one of the following conditions （i） n2（T） ≤△（T） or （ii） there exists a constant c with respect to 0 〈 c 〈 1 such that n2（T） △ cn1（T） and ∑3 ≤d≤△（T）nd（T） ≤ （1 - c）n1（T） ＋ 1.

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.

Acyclic Edge Coloring of 1-planar Graphs without 4-cycles

An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G.The acyclic chromatic index χ'α(G) of G is the smallest k such that G has an acyclic edge coloring using k colors.It was conjectured that every simple graph G with maximum degree Δ has χ'_α(G) ≤Δ+2.A1-planar graph is a graph that can be drawn in the plane so that each edge is crossed by at most one other edge.In this paper,we show that every 1-planar graph G without 4-cycles has χ'_α(G)≤Δ+22.

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.

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.

Neighbor Sum Distinguishing Edge Coloring of Subcubic Graphs

A proper edge-k-coloring of a graph G is a mapping from E（G） to {1, 2,..., k} such that no two adjacent edges receive the same color. A proper edge-k-coloring of G is called neighbor sum distinguishing if for each edge uv ∈ E（G）, the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. Let X（G ） denote the smallest value k in such a ＇ G coloring of G. This parameter makes sense for graphs containing no isolated edges （we call such graphs normal）. The maximum average degree mad（G） of G is the maximum of the average degrees of its non-empty subgraphs. In this paper, we prove that if G is a normal subcubic graph with mad（G） 〈 5 then x＇（G） ≤ 5. We also prove that if G is a normal subcubic graph with at least two 2-vertices, 6 colors are enough for a neighbor sum distinguishing edge coloring of G, which holds for the list version as well.

On the Adjacent Vertex-distinguishing Equitable Edge Coloring of Graphs

Let G（V, E） be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if （1） C（u）≠C（v） for uv ∈ E（G）, where C（u） = {f（uv）｜uv ∈ E}, and （2） for any i, j = 1, 2,… k, we have ｜｜Ei｜ ｜Ej｜｜ ≤ 1, where Ei = {e｜e ∈ E（G） and f（e） = i}. χáve （G） = min{k｜ there exists a k-AVEEC of G} is called the adjacent vertex-distinguishing equitable edge chromatic number of G. In this paper, we obtain the χ áve （G） of some special graphs and present a conjecture.

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.

Acyclic edge coloring of graphs with large girths

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by χ'a(G), is the least number of colors such that G has an acyclic edge k-coloring. Let G be a graph with maximum degree Δ and girth g(G), and let 1≤r≤2Δ be an integer. In this paper, it is shown that there exists a constant c > 0 such that if g(G)≥cΔ r log(Δ2/r) then χa(G)≤Δ + r + 1, which generalizes the result of Alon et al. in 2001. When G is restricted to series-parallel graphs, it is proved that χ'a(G) = Δ if Δ≥4 and g(G)≥4; or Δ≥3 and g(G)≥5.

Acyclic edge coloring of planar graphs without adjacent cycles

A proper edge coloring of a graph G is said to be acyclic if there is no bicolored cycle in G.The acyclic edge chromatic number of G,denoted byχ′a(G),is the smallest number of colors in an acyclic edge coloring of G.Let G be a planar graph with maximum degree.In this paper,we show thatχ′a(G)+2,if G has no adjacent i-and j-cycles for any i,j∈{3,4,5},which implies a result of Hou,Liu and Wu(2012);andχ′a(G)+3,if G has no adjacent i-and j-cycles for any i,j∈{3,4,6}.

Acyclic Edge Coloring of Triangle-free 1-planar Graphs

A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by X＇a（G）, is the least number of colors such that G has an acyclic edge coloring. A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that X＇a（G） ≤△ A（G）＋ 22, if G is a triangle-free 1-planar graph.

On Edge Colorings of 1-Toroidal Graphs

A graph is 1-toroidal, if it can be embedded in the torus so that each edge is crossed by at most one other edge. In this paper, it is proved that every 1-toroidal graph with maximum degree △ ≥ 10 is of class one in terms of edge coloring. Meanwhile, we show that there exist class two 1-toroidal graphs with maximum degree △ for each A ≤ 8.

List Edge Coloring of Outer-1-planar Graphs

A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most once.It is known that the list edge chromatic numberχ′l(G)of any outer-1-planar graph G with maximum degreeΔ(G)≥5 is exactly its maximum degree.In this paper,we proveχ′l(G)=Δ(G)for outer-1-planar graphs G withΔ(G)=4 and with the crossing distance being at least 3.

Edge Coloring by Total Labelings of Outerplanar Graphs

An edge coloring total k-labeling is a labeling of the vertices and the edges of a graph G with labels {1,2,..., k} such that the weights of the edges define a proper edge coloring of G. Here the weight of an edge is the sum of its label and the labels of its two end vertices. This concept was introduce by Brandt et al. They defined Xt＇（G） to be the smallest integer k for which G has an edge coloring total k-labeling and proposed a question： Is there a constant K with X^t（G） ≤△（G）＋1/2 K for all graphs G of maximum degree A（G）？ In this paper, we give a positive answer for outerplanar graphs ≤△（G）＋1/2 by showing that X＇t（G） ≤△（G）＋1/2 for each outerplanar graph G with maximum degree A（G）.

Acyclic Edge Coloring of IC-planar Graphs

A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G.The acyclic chromatic index of G is the least number of colors such that G has an acyclic edge coloring and denoted byχ′a(G).An IC-plane graph is a topological graph where every edge is crossed at most once and no two crossed edges share a vertex.In this paper,it is proved thatχ′a(G)≤Δ(G)+10,if G is an IC-planar graph without adjacent triangles andχ′a(G)≤Δ(G)+8,if G is a triangle-free IC-planar graph.