A note on acyclic edge coloring of complete bipartite graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). Let Delta = Delta(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by K-n,K-n. Alon, McDiarmid and Reed observed that a'(K-p-1,K-p-1) = p for every prime p. In this paper we prove that a'(K-p,K-p) <= p + 2 = Delta + 2 when p is prime. Basavaraju, Chandran and Kummini proved that a'(K-n,K-n) >= n + 2 = Delta + 2 when n is odd, which combined with our result implies that a'(K-p,K-p) = p + 2 = Delta + 2 when p is an odd prime. Moreover we show that if we remove any edge from K-p,K-p, the resulting graph is acyclically Delta + 1 = p + 1-edge-colorable. (C) 2009 Elsevier B.V. All rights reserved.

Acyclic Edge Coloring of Graphs with Maximum Degree 4

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). It was conjectured by Alon, Sudakov, and Zaks that for any simple and finite graph G, a'(G) <= Delta+2, where Delta=Delta(G) denotes the maximum degree of G. We prove the conjecture for connected graphs with Delta(G)<= 4, with the additional restriction that m <= 2n-1, where n is the number of vertices and m is the number of edges in G. Note that for any graph G, m <= 2n, when Delta(G)<= 4. It follows that for any graph G if Delta(G)<= 4, then a'(G) <= 7.

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.

Acyclic Edge-Coloring of Planar Graphs

A proper edge-coloring with the property that every cycle contains edges of at least three distinct colors is called an acyclic edge-coloring. The acyclic chromatic index of a graph G, denoted. chi'(alpha)(G), is the minimum k such that G admits an acyclic edge-coloring with k colors. We conjecture that if G is planar and Delta(G) is large enough, then chi'(alpha) (G) = Delta (G). We settle this conjecture for planar graphs with girth at least 5. We also show that chi'(alpha) (G) <= Delta (G) + 12 for all planar G, which improves a previous result by Fiedorowicz, Haluszczak, and Narayan Inform. Process. Lett., 108 (2008), pp. 412-417].

Acyclic edge coloring of 2-degenerate graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). A graph is called 2-degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2-degenerate graphs properly contains seriesparallel graphs, outerplanar graphs, non - regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a'(G)<=Delta + 2, where Delta = Delta(G) denotes the maximum degree of the graph. We prove the conjecture for 2-degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2-degenerate graph with maximum degree ?, then a'(G)<=Delta + 1. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 68:1-27, 2011

Acyclic Edge Coloring of Triangle-Free Planar Graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a'(G) ? ? + 2, where ? = ?(G) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition |E(H)| ? 2|V(H)|-1, we say that the graph G satisfies Property A. In this article, we prove that if G satisfies Property A, then a'(G) ? ? + 3. Triangle-free planar graphs satisfy Property A. We infer that a'(G) ? ? + 3, if G is a triangle-free planar graph. Another class of graph which satisfies Property A is 2-fold graphs (union of two forests). (C) 2011 Wiley Periodicals, Inc. J Graph Theory

On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem

We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q >= 2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. This problem is NP-hard for q >= 2, and has been well-studied from the point of view of approximation. Our main focus is the case when q = 2, which is already theoretically intricate and practically relevant. We show fixed-parameter tractable algorithms for both the standard and the dual parameter, and for the latter problem, the result is based on a linear vertex kernel.

Rainbow matchings in strongly edge-colored graphs

A rainbow matching of an edge-colored graph G is a matching in which no two edges have the same color. There have been several studies regarding the maximum size of a rainbow matching in a properly edge-colored graph G in terms of its minimum degree 3(G). Wang (2011) asked whether there exists a function f such that a properly edge-colored graph G with at least f (delta(G)) vertices is guaranteed to contain a rainbow matching of size delta(G). This was answered in the affirmative later: the best currently known function Lo and Tan (2014) is f(k) = 4k - 4, for k >= 4 and f (k) = 4k - 3, for k <= 3. Afterwards, the research was focused on finding lower bounds for the size of maximum rainbow matchings in properly edge-colored graphs with fewer than 4 delta(G) - 4 vertices. Strong edge-coloring of a graph G is a restriction of proper edge-coloring where every color class is required to be an induced matching, instead of just being a matching. In this paper, we give lower bounds for the size of a maximum rainbow matching in a strongly edge-colored graph Gin terms of delta(G). We show that for a strongly edge-colored graph G, if |V(G)| >= 2 |3 delta(G)/4|, then G has a rainbow matching of size |3 delta(G)/4|, and if |V(G)| < 2 |3 delta(G)/4|, then G has a rainbow matching of size |V(G)|/2] In addition, we prove that if G is a strongly edge-colored graph that is triangle-free, then it contains a rainbow matching of size at least delta(G). (C) 2015 Elsevier B.V. All rights reserved.

d-Regular Graphs of Acyclic Chromatic Index at Least d+2

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). It was conjectured by Alon, Suclakov and Zaks (and earlier by Fiamcik) that a'(G) <= Delta+2, where Delta = Delta(G) denotes the maximum degree of the graph. Alon et al. also raised the question whether the complete graphs of even order are the only regular graphs which require Delta+2 colors to be acyclically edge colored. In this article, using a simple counting argument we observe not only that this is not true, but in fact all d-regular graphs with 2n vertices and d>n, requires at least d+2 colors. We also show that a'(K-n,K-n) >= n+2, when n is odd using a more non-trivial argument. (Here K-n,K-n denotes the complete bipartite graph with n vertices on each side.) This lower bound for Kn,n can be shown to be tight for some families of complete bipartite graphs and for small values of n. We also infer that for every d, n such that d >= 5, n >= 2d+3 and dn even, there exist d-regular graphs which require at least d+2-colors to be acyclically edge colored. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 63: 226-230, 2010.

Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs

Conditions for the existence of heterochromatic Hamiltonian paths and cycles in edge colored graphs are well investigated in literature. A related problem in this domain is to obtain good lower bounds for the length of a maximum heterochromatic path in an edge colored graph G. This problem is also well explored by now and the lower bounds are often specified as functions of the minimum color degree of G - the minimum number of distinct colors occurring at edges incident to any vertex of G - denoted by v(G). Initially, it was conjectured that the lower bound for the length of a maximum heterochromatic path for an edge colored graph G would be 2v(G)/3]. Chen and Li (2005) showed that the length of a maximum heterochromatic path in an edge colored graph G is at least v(G) - 1, if 1 <= v(G) <= 7, and at least 3v(G)/5] + 1 if v(G) >= 8. They conjectured that the tight lower bound would be v(G) - 1 and demonstrated some examples which achieve this bound. An unpublished manuscript from the same authors (Chen, Li) reported to show that if v(G) >= 8, then G contains a heterochromatic path of length at least 120 + 1. In this paper, we give lower bounds for the length of a maximum heterochromatic path in edge colored graphs without small cycles. We show that if G has no four cycles, then it contains a heterochromatic path of length at least v(G) - o(v(G)) and if the girth of G is at least 4 log(2)(v(G)) + 2, then it contains a heterochromatic path of length at least v(G) - 2, which is only one less than the bound conjectured by Chen and Li (2005). Other special cases considered include lower bounds for the length of a maximum heterochromatic path in edge colored bipartite graphs and triangle-free graphs: for triangle-free graphs we obtain a lower bound of 5v(G)/6] and for bipartite graphs we obtain a lower bound of 6v(G)-3/7]. In this paper, it is also shown that if the coloring is such that G has no heterochromatic triangles, then G contains a heterochromatic path of length at least 13v(G)/17)]. This improves the previously known 3v(G)/4] bound obtained by Chen and Li (2011). We also give a relatively shorter and simpler proof showing that any edge colored graph G contains a heterochromatic path of length at least (C) 2015 Elsevier Ltd. All rights reserved.

Probing the Neutral Edge Modes in Transport across a Point Contact via Thermal Effects in the Read-Rezayi Non-Abelian Quantum Hall States

Non-Abelian quantum Hall states are characterized by the simultaneous appearance of charge and neutral gapless edge modes, with the structure of the latter being intricately related to the existence of bulk quasiparticle excitations obeying non-Abelian statistics. Here we propose a scenario for detecting the neutral modes by having two point contacts in series separated by a distance set by the thermal equilibration length of the charge mode. We show that by using the first point contact as a heating device, the excess charge noise measured at the second point contact carries a nontrivial signature of the presence of the neutral mode. We also obtain explicit expressions for the thermal conductance and corresponding Lorentz number for transport across a quantum point contact between two edges held at different temperatures and chemical potentials.

LIII absorption edge studies of mixed valent cerium intermetallics and related systems

LIII absorption edge measurements clearly delineate 3+ and 4+ states of Ce. Absorption edges of 3+ compounds show a single peak, while those of 4+ compounds show two peaks, both appearing at higher energies than the characteristic peaks of 3+ compounds. In systems where there is interconfigurational fluctuation, features due to both 3+ and 4+ states are distinctly seen.

Effect of inter-edge Coulomb interactions on transport through a point contact in nu=5/2 quantum Hall state

We study transport across a point contact separating two line junctions in a nu = 5/2 quantum Hall system. We analyze the effect of inter-edge Coulomb interactions between the chiral bosonic edge modes of the half-filled Landau level (assuming a Pfaffian wave function for the half-filled state) and of the two fully filled Landau levels. In the presence of inter-edge Coulomb interactions between all the six edges participating in the line junction, we show that the stable fixed point corresponds to a point contact that is neither fully opaque nor fully transparent. Remarkably, this fixed point represents a situation where the half-filled level is fully transmitting, while the two filled levels are completely backscattered; hence the fixed point Hall conductance is given by G(H) = 1/2e(2)/h. We predict the non-universal temperature power laws by which the system approaches the stable fixed point from the two unstable fixed points corresponding to the fully connected case (G(H) = 5/2e(2)/h) and the fully disconnected case (G(H) = 0).

The onset of warps in Spitzer observations of edge-on spiral galaxies

We analyse warps in the nearby edge-on spiral galaxies observed in the Spitzer/Infrared Array Camera (IRAC)4.5-mu m band. In our sample of 24 galaxies, we find evidence of warp in 14 galaxies. We estimate the observed onset radii for the warps in a subsample of 10 galaxies. The dark matter distribution in each of these galaxies are calculated using the mass distribution derived from the observed light distribution and the observed rotation curves. The theoretical predictions of the onset radii for the warps are then derived by applying a self-consistent linear response theory to the obtained mass models for six galaxies with rotation curves in the literature. By comparing the observed onset radii to the theoretical ones, we find that discs with constant thickness can not explain the observations; moderately flaring discs are needed. The required flaring is consistent with the observations. Our analysis shows that the onset of warp is not symmetric in our sample of galaxies. We define a new quantity called the onset-asymmetry index and study its dependence on galaxy properties. The onset asymmetries in warps tend to be larger in galaxies with smaller dis scalelengths. We also define and quantify the global asymmetry in the stellar light distribution, that we call the edge-on asymmetry in edge-on galaxies. It is shown that in most cases the onset asymmetry in warp is actually anticorrelated with the measured edge-on asymmetry in our sample of edge-on galaxies and this could plausibly indicate that the surrounding dark matter distribution is asymmetric.