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.

Max-Coloring Paths: Tight Bounds and Extensions

The max-coloring problem is to compute a legal coloring of the vertices of a graph G = (V, E) with a non-negative weight function w on V such that Sigma(k)(i=1) max(v epsilon Ci) w(v(i)) is minimized, where C-1, ... , C-k are the various color classes. Max-coloring general graphs is as hard as the classical vertex coloring problem, a special case where vertices have unit weight. In fact, in some cases it can even be harder: for example, no polynomial time algorithm is known for max-coloring trees. In this paper we consider the problem of max-coloring paths and its generalization, max-coloring abroad class of trees and show it can be solved in time O(vertical bar V vertical bar+time for sorting the vertex weights). When vertex weights belong to R, we show a matching lower bound of Omega(vertical bar V vertical bar log vertical bar V vertical bar) in the algebraic computation tree model.

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.

Polymer optoelectronic structures for retinal prosthesis

This commentary highlights the effectiveness of optoelectronic properties of polymer semiconductors based on recent results emerging from our laboratory, where these materials are explored as artificial receptors for interfacing with the visual systems. Organic semiconductors based polymer layers in contact with physiological media exhibit interesting photophysical features, which mimic certain natural photoreceptors, including those in the retina. The availability of such optoelectronic materials opens up a gateway to utilize these structures as neuronal interfaces for stimulating retinal ganglion cells. In a recently reported work entitled ``A polymer optoelectronic interface provides visual cues to a blind retina,'' we utilized a specific configuration of a polymer semiconductor device structure to elicit neuronal activity in a blind retina upon photoexcitation. The elicited neuronal signals were found to have several features that followed the optoelectronic response of the polymer film. More importantly, the polymer-induced retinal response resembled the natural response of the retina to photoexcitation. These observations open up a promising material alternative for artificial retina applications.

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.

Are component positioning and prosthesis size associated with hip resurfacing failure?

BACKGROUND: Recent studies suggest that there is a learning curve for metal-on-metal hip resurfacing. The purpose of this study was to assess whether implant positioning changed with surgeon experience and whether positioning and component sizing were associated with implant longevity. METHODS: We evaluated the first 361 consecutive hip resurfacings performed by a single surgeon, which had a mean follow-up of 59 months (range, 28 to 87 months). Pre and post-operative radiographs were assessed to determine the inclination of the acetabular component, as well as the sagittal and coronal femoral stem-neck angles. Changes in the precision of component placement were determined by assessing changes in the standard deviation of each measurement using variance ratio and linear regression analysis. Additionally, the cup and stem-shaft angles as well as component sizes were compared between the 31 hips that failed over the follow-up period and the surviving components to assess for any differences that might have been associated with an increased risk for failure. RESULTS: Surgeon experience was correlated with improved precision of the antero-posterior and lateral positioning of the femoral component. However, femoral and acetabular radiographic implant positioning angles were not different between the surviving hips and failures. The failures had smaller mean femoral component diameters as compared to the non-failure group (44 versus 47 millimeters). CONCLUSIONS: These results suggest that there may be differences in implant positioning in early versus late learning curve procedures, but that in the absence of recognized risk factors such as intra-operative notching of the femoral neck and cup inclination in excess of 50 degrees, component positioning does not appear to be associated with failure. Nevertheless, surgeons should exercise caution in operating patients with small femoral necks, especially when they are early in the learning curve.

Percutaneous Revision of a Testicular Prosthesis is Safe, Cost-effective, and Provides Good Patient Satisfaction.

Office-based percutaneous revision of a testicular prosthesis has never been reported. A patient received a testicular prosthesis but was dissatisfied with the firmness of the implant. In an office setting, the prosthesis was inflated with additional fluid via a percutaneous approach. Evaluated outcomes included patient satisfaction, prosthesis size, recovery time, and cost savings. The patient was satisfied, with no infection, leak, or complication after more than 1 year of follow-up, at significantly less cost than revision surgery. Percutaneous adjustment of testicular prosthesis fill-volume can be safe, inexpensive, and result in good patient satisfaction.

Computer simulating a trial of a load-bearing implant: example of an intramedullary prosthesis

Computational modelling is becoming ever more important for obtaining regulatory approval for new medical devices. An accepted approach is to infer performance in a population from an analysis conducted for an idealised or ‘average’ patient; we present here a method for predicting the performance of an orthopaedic implant when released into a population—effectively simulating a clinical trial. Specifically we hypothesise that an analysis based on a method for predicting the performance in a population will lead to different conclusions than an analysis based on an idealised or ‘average’ patient. To test this hypothesis we use a finite element model of an intramedullary implant in a bone whose size and remodelling activity is different for each individual in the population. We compare the performance of a low Young’s modulus implant (View the MathML source) to one with a higher Young’s modulus (200 GPa). Cyclic loading is applied and failure is assumed when the migration of the implant relative to the bone exceeds a threshold magnitude. The analysis for an idealised of ‘average’ patient predicts that the lower modulus device survives longer whereas the analysis simulating a clinical trial predicts no statistically-significant tendency (p=0.77) for the low modulus device to perform better. It is concluded that population-based simulations of implant performance–simulating a clinical trial–present a very valuable opportunity for more realistic computational pre-clinical testing of medical devices.