Acyclic and k-distance coloring of the grid

In this paper, we give a relatively simple though very efficient way to color the d-dimensional grid G(n₁,n₂,…,n_d) (with n_i vertices in each dimension 1?i?d), for two different types of vertex colorings: (1) acyclic coloring of graphs, in which we color the vertices such that (i) no two neighbors are assigned the same color and (ii) for any two colors i and j, the subgraph induced by the vertices colored i or j is acyclic; and (2) k-distance coloring of graphs, in which every vertex must be colored in such a way that two vertices lying at distance less than or equal to k must be assigned different colors. The minimum number of colors needed to acyclically color (respectively k-distance color) a graph G is called acyclic chromatic number of G (respectively k-distance chromatic number), and denoted a(G) (respectively χ_k(G)).The method we propose for coloring the d-dimensional grid in those two variants relies on the representation of the vertices of G_d(n₁,…,n_d) thanks to its coordinates in each dimension; this gives us upper bounds on a(G_d(n₁,…,n_d)) and χ_k(G_d(n₁,…,n_d)).We also give lower bounds on a(G_d(n₁,…,n_d)) and χ_k(G_d(n₁,…,n_d)). In particular, we give a lower bound on a(G) for any graph G; surprisingly, as far as we know this result was never mentioned before. Applied to the d-dimensional grid G_d(n₁,…,n_d), the lower and upper bounds for a(G_d(n₁,…,n_d)) match (and thus give an optimal result) when the lengths in each dimension are “sufficiently large” (more precisely, if ). If this is not the case, then these bounds differ by an additive constant at most equal to . Concerning χ_k(G_d(n₁,…,n_d)), we give exact results on its value for (1) k=2 and any d?1, and (2) d=2 and any k?1.In the case of acyclic coloring, we also apply our results to hypercubes of dimension d, H_d, which are a particular case of G_d(n₁,…,n_d) in which there are only 2 vertices in each dimension. In that case, the bounds we obtain differ by a multiplicative constant equal to 2.     

A note on the online First-Fit algorithm for coloring k-inductive graphs

In a FOCS 1990 paper, S. Irani proved that the First-Fit online algorithm for coloring a graph uses at most O(klogn) colors for k-inductive graphs. In this note we provide a very short proof of this fact.     

An algorithm for computing simple k-factors

A k-factor of graph G is defined as a k-regular spanning subgraph of G. For instance, a 2-factor of G is a set of cycles that span G. 2-factors have multiple applications in Graph Theory, Computer Graphics, and Computational Geometry. We define a simple 2-factor as a 2-factor without degenerate cycles. In general, simple k-factors are defined as k-regular spanning subgraphs where no edge is used more than once. We propose a new algorithm for computing simple k-factors for all values of k?2.     

A constant approximation algorithm for the densest k-subgraph problem on chordal graphs

The densest k-subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The DkS problem is NP-hard even for special graph classes including bipartite, planar, comparability and chordal graphs, while no constant approximation algorithm is known for any of these classes. In this paper we present a 3-approximation algorithm for the class of chordal graphs. The analysis of our algorithm is based on a graph theoretic lemma of independent interest.     

On the additive constant of the k-server Work Function Algorithm

We consider the Work Function Algorithm for the k-server problem (Chrobak and Larmore, 1991; Koutsoupias and Papadimitriou, 1995) [2] and [4]. We show that if the Work Function Algorithm is c-competitive, then it is also strictly(2c)-competitive. As a consequence of (Koutsoupias and Papadimitriou, 1995) [4] this also shows that the Work Function Algorithm is strictly (4k−2)-competitive.     

The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones

Given a graph G, a spanning subgraph H of G   and an integer λ≥2$\lambda \ge 2$, a λ-backbone coloring of G with backbone H is a proper vertex coloring of G   using colors 1,2,…$1,2,\dots$, in which the color difference between vertices adjacent in H is greater than or equal to λ. The backbone coloring problem is that of finding such a coloring whose maximum color does not exceed a given limit k  . In this paper, we study the backbone coloring problem for bounded-degree graphs with connected backbones and we give a complete computational complexity classification of this problem. We present a polynomial algorithm for optimal backbone coloring for subcubic graphs with arbitrary backbones. We also prove that the backbone coloring problem for graphs with arbitrary backbones and with fixed maximum degree (at least 4) is NP-complete. Furthermore, we show that for the special case of graphs with fixed maximum degree at least 5 and λ≥4$\lambda \ge 4$ the problem remains NP-complete even for spanning tree backbones.     

On acyclic edge coloring of toroidal graphs

Let c be a proper edge coloring of a graph G. If there exists no bicolored cycle in G with respect to c, then c is called an acyclic edge coloring of G. Let G be a planar graph with maximum degree Δ and girth g. In Dong and Xu (2010) [8], Dong and Xu proved that G admits an acyclic edge coloring with Δ(G) colors if Δ?8 and g?7, or Δ?6 and g?8, or Δ?5 and g?9, or Δ?4 and g?10, or Δ?3 and g?14. In this note, we fix a small gap in the proof of Dong and Xu (2010) [8], and generalize the above results to toroidal graphs.     

A Fan-type result on k-ordered graphs

For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. In this paper, we show that if G is a ⌊3k/2⌋-connected graph of order n?100k, and d(u)+d(v)?n for any two vertices u and v with d(u,v)=2, then G is k-ordered hamiltonian. Our result implies the theorem of G. Chen et al. [Ars Combin. 70 (2004) 245-255] [1], which requires the degree sum condition for all pairs of non-adjacent vertices, not just those distance 2 apart.     

Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth

We present a generic scheme for approximating NP-hard problems on graphs of treewidth k=ω(logn). When a tree-decomposition of width ? is given, the scheme typically yields an ?/logn-approximation factor; otherwise, an extra logk factor is incurred. Our method applies to several basic subgraph and partitioning problems, including the maximum independent set problem.     

On α-redundant vertices in P5-free graphs

We prove that Maximum Stable Set can be solved in polynomial time on two new subclasses of P₅-free graphs, extending some known polynomially solvable cases.     

The bottleneck k-MST

The k-MST is a well known NP-hard problem and several approximation algorithms exist to solve this problem with a guaranteed performance bound. A closely related problem, called the bottleneck k-MST (BMST(k)) can however be solved in O(mlogn) time on graph with n nodes and m edges. We propose two algorithms to solve BMST(k), one of complexity O(m+nlogn) and the other of O(m) time. We also consider a generalization of BMST(k) which subsumes many bottleneck problems studied in the literature and show that this generalized problem can also be solved in O(m) time.     

Online coloring of hypergraphs

We give a tight bound on randomized online coloring of hypergraphs. The bound holds even if the algorithm knows the hypergraph in advance (but not the ordering in which it is presented). More specifically, we show that for any n and k, there is a 2-colorable k-uniform hypergraph on n vertices for which any randomized online coloring uses Ω(n/k) colors in expectation.     

Acyclic coloring of graphs of maximum degree five: Nine colors are enough

An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic number of G is the least number of colors necessary to acyclically color G. In this paper, we show that any graph of maximum degree 5 has acyclic chromatic number at most 9, and we give a linear time algorithm that achieves this bound.     

Expected parallel time and sequential space complexity of graph and digraph problems

This paper determines upper bounds on the expected time complexity for a variety of parallel algorithms for undirected and directed random graph problems. For connectivity, biconnectivity, transitive closure, minimum spanning trees, and all pairs minimum cost paths, we prove the expected time to beO(log logn) for the CRCW PRAM (this parallel RAM machine allows resolution of write conflicts) andO(logn · log logn) for the CREW PRAM (which allows simultaneous reads but not simultaneous writes). We also show that the problem of graph isomorphism has expected parallel timeO(log logn) for the CRCW PRAM andO(logn) for the CREW PRAM. Most of these results follow because of upper bounds on the mean depth of a graph, derived in this paper, for more general graphs than was known before.For undirected connectivity especially, we present a new probabilistic algorithm which runs on a randomized input and has an expected running time ofO(log logn) on the CRCW PRAM, withO(n) expected number of processors only.Our results also improve known upper bounds on the expected space required for sequential graph algorithms. For example, we show that the problems of finding connected components, transitive closure, minimum spanning trees, and minimum cost paths have expected sequential spaceO(logn · log logn) on a deterministic Turing Machine. We use a simulation of the CRCW PRAM to get these expected sequential space bounds.This research was supported by National Science Foundation Grant DCR-85-03251 and Office of Naval Research Contract N00014-80-C-0647.This research was partially supported by the National Science Foundation Grants MCS-83-00630, DCR-8503497, by the Greek Ministry of Research and Technology, and by the ESPRIT Basic Research Actions Project ALCOM.     

Constructing vertex-disjoint paths in (n, k)-star graphs

This work describes a novel routing algorithm for constructing a container of width n − 1 between a pair of vertices in an (n, k)-star graph with connectivity n − 1. Since Lin et al. [T.C. Lin, D.R. Duh, H.C. Cheng, Wide diameter of (n, k)-star networks, in: Proceedings of the International Conference on Computing, Communications and Control Technologies, vol. 5, 2004, pp. 160-165] already calculated the wide diameters in (n, n − 1)-star and (n, 1)-star graphs, this study only considers an (n, k)-star with 2 ? k ? n − 2. The length of the longest container among all constructed containers serves as the upper bound of the wide diameter of an (n, k)-star graph. The lower bound of the wide diameter of an (n, k)-star graph with 2 ? k ? ⌊n/2⌋ and the lower bound of the wide diameter of a regular graph with a connectivity of 2 or above are also computed. Measurement results indicate that the wide diameter of an (n, k)-star graph is its diameter plus 2 for 2 ? k ? ⌊n/2⌋, or its diameter plus a value between 1 and 2 for ⌊n/2⌋ + 1 ? k ? n − 2.     

Linear structure of bipartite permutation graphs and the longest path problem

The class of bipartite permutation graphs is the intersection of two well known graph classes: bipartite graphs and permutation graphs. A complete bipartite decomposition of a bipartite permutation graph is proposed in this note. The decomposition gives a linear structure of bipartite permutation graphs, and it can be obtained in O(n) time, where n is the number of vertices. As an application of the decomposition, we show an O(n) time and space algorithm for finding a longest path in a bipartite permutation graph.