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 ∨ 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 S_f(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 coloring 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 SAedge chromatic number for short,and denoted byχ'_(sa)(G).In this paper,we have discussed the SA-edge chromatic number of K_4∨K_n.

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.

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.

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.

Improved Upper Bounds on Acyclic Edge Colorings

An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors. The acyclic chromatic index of a graph G, denoted by a＇（G）, is the minimum number k such that there is an acyclic edge coloring using k colors. It is known that a＇（G） ≤ 16△ for every graph G where △denotes the maximum degree of G. We prove that a＇（G） 〈 13.8A for an arbitrary graph G. We also reduce the upper bounds of a＇（G） to 9.8△ and 9△ with girth 5 and 7, respectively.

On f-edge Cover Chromatic Index of Multigraphs

Let G be a multigraph with vertex set V（G）. Assume that a positive integer f（v） with 1 ≤ f（v） ≤ d（v） is associated with each vertex v ∈ V. An edge coloring of G is called an f-edge cover-coloring, if each color appears at each vertex v at least f（v） times. Let X＇fc（G） be the maximum positive integer k for which an f-edge cover-coloring with k colors of G exists. In this paper, we give a new lower bound of X＇fc（G）, which is sharp.

GRAPH COLORING BASED CHANNEL ASSIGNMENT FRAMEWORK FOR RURAL WIRELESS MESH NETWORKS

IEEE 802.11 based wireless mesh networks with directional antennas are expected to be a new promising technology and an economic approach for providing wireless broadband services in rural areas.In this paper,we discuss interference models and address how they can affect the design of channel assignment in rural mesh networks.We present a new channel assignment framework based on graph coloring for rural wireless mesh networks.The goal of the framework is to allow synchronously transmitting or receiving data from multiple neighbor links at the same time,and continuously doing full-duplex data transfer on every link,creating an efficient rural mesh network without interference.Channel assignment is shown to be NP-hard.We frame this channel allocation problem in terms of Adjacent Vertex Distinguishing Edge Coloring(AVDEC).Detailed assignment results on grid topology are presented and discussed.Furthermore,we design an algorithm.Finally,we evaluate the performance of the proposed algorithm through extensive simulations and show the algorithm is effective to the regular grid topologies,and the number of colors used by the algorithm is upper bounded by+1.Hence the algorithm guarantees that the number of channels available in standards such as IEEE802.11a is sufficient to have a valid AVDEC for many grid topologies.We also evaluate the proposed algorithm for arbitrary graphs.The algorithm provides a lower upper bound on the minimum number of channels to the AVDEC index channel assignment problem.

A ROBUST COLOR EDGE DETECTION ALGORITHM BASED ON THE QUATERNION HARDY FILTER

This paper presents a robust filter called the quaternion Hardy filter(QHF)for color image edge detection.The QHF can be capable of color edge feature enhancement and noise resistance.QHF can be used flexibly by selecting suitable parameters to handle different levels of noise.In particular,the quaternion analytic signal,which is an effective tool in color image processing,can also be produced by quaternion Hardy filtering with specific parameters.Based on the QHF and the improved Di Zenzo gradient operator,a novel color edge detection algorithm is proposed;importantly,it can be efficiently implemented by using the fast discrete quaternion Fourier transform technique.From the experimental results,we conclude that the minimum PSNR improvement rate is 2.3%and the minimum SSIM improvement rate is 30.2%on the CSEE database.The experiments demonstrate that the proposed algorithm outperforms several widely used algorithms.

Neighbor Sum Distinguishing Index of Graphs with Maximum Average Degree

A proper k-edge coloring of a graph G = (V(G), E(G)) is an assignment c: E(G) → {1, 2, …, k} such that no two adjacent edges receive the same color. A neighbor sum distinguishing k-edge coloring of G is a proper k-edge coloring of G such that for each edge uv ∈ E(G). The neighbor sum distinguishing index of a graph G is the least integer k such that G has such a coloring, denoted by χ’Σ(G). Let be the maximum average degree of G. In this paper, we prove χ’Σ(G) ≤ max{9, Δ(G) +1} for any normal graph G with . Our approach is based on the discharging method and Combinatorial Nullstellensatz.