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.

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.

Some Results on Edge Cover Coloring of Double Graphs

Let G be a simple graph with vertex set V(G) and edge set E(G). An edge coloring C of G is called an edge cover coloring, if each color appears at least once at each vertex . The maximum positive integer k such that G has a k edge cover coloring is called the edge cover chromatic number of G and is denoted by . It is known that for any graph G, . If , then G is called a graph of CI class, otherwise G is called a graph of CII class. It is easy to prove that the problem of deciding whether a given graph is of CI class or CII class is NP-complete. In this paper, we consider the classification on double graph of some graphs and a polynomial time algorithm can be obtained for actually finding such a classification by our proof.

The 4-Acyclic Edge Coloring of Graphs with Large Girths

A proper edge coloring of a graph is acyclic, if every cycle of the graph has at least 3 colors. Let r be a positive integer. An edge coloring is r-acyclic if it is proper and every cycle C has at least ?colors. The r-acyclic edge chromatic ??number of a graph G?is the minimum number of colors needed for any r-acyclic edge coloring of G. When r=4, the result of this paper is that the 4-acyclic chromatic number of a graph with maximum degree Δ and girth ?is less than 18Δ. Furthermore, if the girth of graph G?is at least , then .

A Non-Conventional Coloring of the Edges of a Graph

Coloring the nodes of a graph is a commonly used technique to speed up clique search algorithms. Coloring the edges of the graph as a preconditioning method can also be used to speed up computations. In this paper we will show that an unconventional coloring scheme of the edges leads to an NP-complete problem when one intends to determine the optimal number of colors.

On a Number of Colors in 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 its vertex x, 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. For an arbitrary simple cycle, all possible values of t are found, for which the graph has a cyclically interval t-coloring.

Edge Colorings of Planar Graphs without 6-Cycles with Two Chords

It is proved here that if a planar graph has maximum degree at least 6 and any 6-cycle contains at most one chord, then it is of class 1.

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.

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

Note on 2-edge-colorings of complete graphs with small monochromatic k-connected subgraphs

Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when n 〉 13k - 15. In this note, we characterize all the 2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n - 2k ＋ 2 vertices for n ≥ 13k - 15.

Cost Edge-Coloring of a Cactus

Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different colors. The cost ?of an edge-coloring f of G is the sum of costs ?of colors ?assigned to all edges e in G. An edge-coloring f of G is optimal if ?is minimum among all edge-colorings of G. A cactus is a connected graph in which every block is either an edge or a cycle. In this paper, we give an algorithm to find an optimal edge- ??coloring of a cactus in polynomial time. In our best knowledge, this is the first polynomial-time algorithm to find an optimal edge-coloring of a cactus.

Feature fusion method for edge detection of color images

A novel feature fusion method is proposed for the edge detection of color images. Except for the typical features used in edge detection, the color contrast similarity and the orientation consistency are also selected as the features. The four features are combined together as a parameter to detect the edges of color images. Experimental results show that the method can inhibit noisy edges and facilitate the detection for weak edges. It has a better performance than conventional methods in noisy environments.

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.

AN ADAPTIVE COLOR PLANE INTERPOLATION METHOD BASED ON EDGE DETECTION

In this letter, an adaptive interpolation algorithm based on edge detection is proposed. With this algorithm, all the missing green values can be reconstructed in Bayer pattern image by using edge detection interpolation method. Reconstructed images composed of green pixels are classified according to the high frequency components in image, and the threshold T needed for all kinds of green images in the edge detection is determined through experiments. The edge detection is carried out based on the one Dimensional (1D) gradient operator. If the gradient value is greater than T, this pixel is located on the edge; otherwise the pixel is in the smooth area of the image. Finally, the simple bilinear interpolation is used for the smooth area while the Laplacian interpolation with the second-order correction term is adopted to reconstruct the other red/blue values on the edge. This algorithm resolves effectively the conflicts between reconstructing high quality color image and reducing computational complexity, and thus largely enhances the processing speed for the reconstructed color image.

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