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.

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.