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

Conflict-Free Coloring for Rectangle Ranges Using O(n.382) Colors

Given a set of points P ⊆ R2, a conflict-free coloring of P w.r.t. rectangle ranges is an assignment of colors to points of P, such that each nonempty axisparallel rectangle T in the plane contains a point whose color is distinct from all other points in P ∩ T . This notion has been the subject of recent interest and is motivated by frequency assignment in wireless cellular networks: one naturally would like to minimize the number of frequencies (colors) assigned to base stations (points) such that within any range (for instance, rectangle), there is no interference. We show that any set of n points in R2 can be conflict-free colored with O(nβ∗+o(1)) colors in expected polynomial time, where β∗ = 3−√5 2 < 0.382.

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

Higher-Dimensional Analogues of the Map Coloring Problem

After a brief discussion of the history of the problem, we propose a generalization of the map coloring problem to higher dimensions.

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.

An analysis of migratory salmonid catch effort data, derived from anglers' log books, 1991

1000 log books were issued to anglers of which 236 were returned, those from the rivers Derwent, Kent, Lune and Ribble accounted for the vast majority. The Derwent had the highest catch rate of these rivers: one salmon every 13.89 hours followed by the Lune, Kent and Ribble at 16.39, 18.87 and 35.71 hours, respectively. For sea trout the Lune, Derwent and Ribble had a catch rate of approximately one fish every 10.0 hours (9.8, 10.0 and 10.64 hours),and for the Kent one fish per 16.1 hours fished. Salmon angling visits were, in general,longer than those for sea trout being between 2 and 6 hours as opposed to 2 to 4 hours. On the majority of visits (>80%) no fish were caught and was the same for salmon and sea trout. For salmon the majority of fish were caught on fly, spinner or worm, and the least on prawn. For sea trout fly predominated. The majority of salmon caught were less than 91b in weight and were presumed to be grilse (1 sea winter). The majority of the sea trout caught weighed between 1 and 31b. The pattern of catch, effort, CPUE, abundance and catchability for salmon and sea trout were modelled using the data from the rivers Derwent, Kent and Lune. Flow significantly influenced catch, effort and catchability of salmon which had entered in a particular month. For sea trout flow was not significantly correlated with any of the dependent variables. The catchability coefficient for salmon, determined from the total number of fish, remained relatively constant over the period June to October indicating that CPUE was a reasonable measure of within season abundance. This was not found to be the case for sea trout.

Three new Galapagos books

Contents for three books: Galapagos: Volume 2 edited by Roger Perry. Evolution in the Galapagos edited by R.J. Berry. Patterns of Evolution in Galapagos Organisms edited by Robert I. Bowman, Margaret Berson and Alan E. Leviton.