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.

Color constancy using color edge moments and regularized regression in anchored neighborhood

To improve the accuracy of illumination estimation while maintaining a relative fast execution speed, a novel learning-based color constancy using color edge moments and regularized regression in an anchored neighborhood is proposed. First, scene images are represented by the color edge moments of various orders. Then, an iterative regression with a squared Frobenius norm（F-norm） regularizer is introduced to learn the mapping between the edge moments and illuminants in the neighborhood of the anchored sample.Illumination estimation for the test image finally becomes the nearest anchored point search followed by a matrix multiplication using the associated mapping matrix which can be precalculated and stored. Experiments on two standard image datasets show that the proposed approach significantly outperforms the state-of-the-art algorithms with a performance increase of at least 10. 35% and 7. 44% with regard to median angular error.

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.

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.

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.

A New Method of Color Edge Detection Based on Local Structure Analysis

Human's real life is within a colorful world. Compared to the gray images, color images contain more information and have better visual effects. In today's digital image processing, image segmentation is an important section for computers to "understand" images and edge detection is always one of the most important methods in the field of image segmentation. Edges in color images are considered as local discontinuities both in color and spatial domains. Despite the intensive study based on integration of single-channel edge detection results, and on vector space analysis, edge detection in color images remains as a challenging issue.

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”.

Three-Rainbow Coloring of Split Graphs

After a necessary condition is given, 3-rainbow coloring of split graphs with time complexity O(m) is obtained by constructive method. The number of corresponding colors is at most 2 or 3 more than the minimum number of colors needed in a 3-rainbow coloring.

Upper bounds on vertex distinguishing chromatic index of some Halin graphs

A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph C is denoted by Xs＇8（G）. In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with △（G） ≥ 4, respectively.

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.

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.

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.

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△.

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.