Approximations for node-weighted Steiner tree in unit disk graphs

Given a node-weighted connected graph and a subset of terminals, the problem node-weighted Steiner tree (NWST) seeks a lightest tree connecting a given set of terminals in a node-weighted graph. While NWST in general graphs are as hard as Set Cover, NWST restricted to unit-disk graphs (UDGs) admits constant-approximations. Recently, Zou et al. (Lecture notes in computer science, vol 5165, COCOA, 2008, pp 278–285) showed that any μ-approximation algorithm for the classical edge-weighted Steiner tree problem can be used to produce 2.5 μ-approximation algorithm for NWST restricted to UDGs. With the best known approximation bound 1.55 for the classical Steiner tree problem, they obtained an approximation bound 3.875 for NWST restricted to UDGs. In this paper, we present three approximation algorithms for NWST restricted to UDGs, the k-Restricted Relative Greedy Algorithm whose approximation bound converges to 1 + ln 5 ≈ 2.61 as k → ∞, the 3-Restricted Greedy Algorithm with approximation bound 4\frac13{4\frac{1}{3}} , and the k-Restricted Variable Metric Algorithm whose approximation bound converges to 3.9334 as k → ∞.     

Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees

We study graph multicoloring problems, motivated by the scheduling of dependent jobs on multiple machines. In multicoloring problems, vertices have lengths which determine the number of colors they must receive, and the desired coloring can be either contiguous (nonpreemptive schedule) or arbitrary (preemptive schedule). We consider both the sum-of-completion times measure, or the sum of the last color assigned to each vertex, as well as the more common makespan measure, or the number of colors used. In this paper, we study two fundamental classes of graphs: planar graphs and partial k-trees. For both classes, we give a polynomial time approximation scheme (PTAS) for the multicoloring sum, for both the preemptive and nonpreemptive cases. On the other hand, we show the problem to be strongly NP-hard on planar graphs, even in the unweighted case, known as the sum coloring problem. For a nonpreemptive multicoloring sum of partial k-trees, we obtain a fully polynomial time approximation scheme. This is based on a pseudo-polynomial time algorithm that holds for a general class of cost functions. Finally, we give a PTAS for the makespan of a preemptive multicoloring of partial k-trees that uses only O(log n) preemptions. These results are based on several properties of multicolorings and tools for manipulating them, which may be of more general applicability.     

Analysing local algorithms in location-aware quasi-unit-disk graphs

A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds; here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node.We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set.We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs.     

The circular chromatic number of a digraph

We introduce the circular chromatic number χ_c of a digraph and establish various basic results. They show that the coloring theory for digraphs is similar to the coloring theory for undirected graphs when independent sets of vertices are replaced by acyclic sets. Since the directed k‐cycle has circular chromatic number k/(k – 1), for k ≥ 2, values of χ_c between 1 and 2 are possible. We show that in fact, χ_c takes on all rational values greater than 1. Furthermore, there exist digraphs of arbitrarily large digirth and circular chromatic number. It is NP‐complete to decide if a given digraph has χ_c at most 2. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 227–240, 2004     

Complexity of clique‐coloring odd‐hole‐free graphs

In this paper we investigate the problem of clique‐coloring, which consists in coloring the vertices of a graph in such a way that no monochromatic maximal clique appears, and we focus on odd‐hole‐free graphs. On the one hand we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, but on the other hand it is NP‐hard to decide if they are 2‐clique‐colorable, and we do not know if there exists any bound k₀ such that they are all k₀ ‐clique‐colorable. First we will prove that (odd hole, codiamond)‐free graphs are 2‐clique‐colorable. Then we will demonstrate that the complexity of 2‐clique‐coloring odd‐hole‐free graphs is actually Σ₂ P‐complete. Finally we will study the complexity of deciding whether or not a graph and all its subgraphs are 2‐clique‐colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 139–156, 2009     

The harmonious coloring problem is NP-complete for interval and permutation graphs

In this paper, we prove that the harmonious coloring problem is NP-complete for connected interval and permutation graphs. Given a simple graph G, a harmonious coloring of G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number is the least integer k for which G admits a harmonious coloring with k colors. Extending previous work on the NP-completeness of the harmonious coloring problem when restricted to the class of disconnected graphs which are simultaneously cographs and interval graphs, we prove that the problem is also NP-complete for connected interval and permutation graphs.     

NP‐completeness of list coloring and precoloring extension on the edges of planar graphs

In the edge precoloring extension problem, we are given a graph with some of the edges having preassigned colors and it has to be decided whether this coloring can be extended to a proper k‐edge‐coloring of the graph. In list edge coloring every edge has a list of admissible colors, and the question is whether there is a proper edge coloring where every edge receives a color from its list. We show that both problems are NP‐complete on (a) planar 3‐regular bipartite graphs, (b) bipartite outerplanar graphs, and (c) bipartite series‐parallel graphs. This improves previous results of Easton and Parker 6 , and Fiala 8 . © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 313–324, 2005     

Minimum Color Sum of Bipartite Graphs

The problem ofminimum color sumof a graph is to color the vertices of the graph such that the sum (average) of all assigned colors is minimum. Recently it was shown that in general graphs this problem cannot be approximated withinn^{1 − ε}, for any ε > 0, unlessNP = ZPP(Bar-Noyet al., Information and Computation140(1998), 183–202). In the same paper, a 9/8-approximation algorithm was presented for bipartite graphs. The hardness question for this problem on bipartite graphs was left open. In this paper we show that the minimum color sum problem for bipartite graphs admits no polynomial approximation scheme, unlessP = NP. The proof is byL-reducing the problem of finding the maximum independent set in a graph whose maximum degree is four to this problem. This result indicates clearly that the minimum color sum problem is much harder than the traditional coloring problem, which is trivially solvable in bipartite graphs. As for the approximation ratio, we make a further step toward finding the precise threshold. We present a polynomial 10/9-approximation algorithm. Our algorithm uses a flow procedure in addition to the maximum independent set procedure used in previous solutions.     

Mutual exclusion scheduling with interval graphs or related classes. Part II

This paper is the second part of a study devoted to the mutual exclusion scheduling problem. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. The cardinality of such a coloring is denoted by χ(G,k). When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be NP-hard for interval graphs, even if k is a constant greater than or equal to four [H.L. Bodlaender, K. Jansen, Restrictions of graph partition problems. Part I. Theoret. Comput. Sci. 148 (1995) 93-109]. In this paper, the problem is approached from a different point of view by studying a non-trivial and practical sufficient condition for optimality. In particular, the following proposition is demonstrated: if an interval graph G admits a coloring such that each color appears at least k times, then χ(G,k)=⌈n/k⌉. This proposition is extended to several classes of graphs related to interval graphs. Moreover, all our proofs are constructive and provide efficient algorithms to solve the MES problem for these graphs, given a coloring satisfying the condition in input.     

On connected domination in unit ball graphs

Given a simple undirected graph, the minimum connected dominating set problem is to find a minimum cardinality subset of vertices D inducing a connected subgraph such that each vertex outside D has at least one neighbor in D. Approximations of minimum connected dominating sets are often used to represent a virtual routing backbone in wireless networks. This paper first proposes a constant-ratio approximation algorithm for the minimum connected dominating set problem in unit ball graphs and then introduces and studies the edge-weighted bottleneck connected dominating set problem, which seeks a minimum edge weight in the graph such that the corresponding bottleneck subgraph has a connected dominating set of size k. In wireless network applications this problem can be used to determine an optimal transmission range for a network with a predefined size of the virtual backbone. We show that the problem is hard to approximate within a factor better than 2 in graphs whose edge weights satisfy the triangle inequality and provide a 3-approximation algorithm for such graphs. We also show that for fixed k the problem is polynomially solvable in unit disk and unit ball graphs.     

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

We study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighted node coloring is NP-hard in P₈-free bipartite graphs, but polynomial for P₅-free bipartite graphs. We next focus on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with min weighted edge coloring in bipartite graphs. We show that this problem remains strongly NP-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6−ε, for any ε>0 and we give an approximation algorithm with the same ratio. Finally, we show that min weighted node coloring in split graphs can be solved by a polynomial time approximation scheme.     

Disjoint paths in sparse graphs

We generalize all the results obtained for maximum integer multiflow and minimum multicut problems in trees by Garg, Vazirani and Yannakakis [N. Garg, V.V. Vazirani, M. Yannakakis, Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica 18 (1997) 3–20] to graphs with a fixed cyclomatic number, while this cannot be achieved for other classical generalizations of trees. We also introduce thek-edge-outerplanar graphs, a class of planar graphs with arbitrary (but bounded) tree-width that generalizes the cacti, and show that the integrality gap of the maximum edge-disjoint paths problem is bounded in these graphs.     

Odd 4‐edge‐colorability of graphs

An odd k‐edge‐coloring of a graph G is a (not necessarily proper) edge‐coloring with at most k colors such that each nonempty color class induces a graph in which every vertex is of odd degree. Pyber (1991) showed that every simple graph is odd 4‐edge‐colorable, and Lužar et al. (2015) showed that connected loopless graphs are odd 5‐edge‐colorable, with one particular exception that is odd 6‐edge‐colorable. In this article, we prove that connected loopless graphs are odd 4‐edge‐colorable, with two particular exceptions that are respectively odd 5‐ and odd 6‐edge‐colorable. Moreover, a color class can be reduced to a size at most 2.     

On total 9‐coloring planar graphs of maximum degree seven

Given a graph G, a total k‐coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If Δ(G) is the maximum degree of G, then no graph has a total Δ‐coloring, but Vizing conjectured that every graph has a total (Δ + 2)‐coloring. This Total Coloring Conjecture remains open even for planar graphs. This article proves one of the two remaining planar cases, showing that every planar (and projective) graph with Δ ≤ 7 has a total 9‐coloring by means of the discharging method. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 67–73, 1999     

A Characterization of b‐Perfect Graphs

A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b‐chromatic number of a graph G is the largest integer k such that G admits a b‐coloring with k colors. A graph is b‐perfect if the b‐chromatic number is equal to the chromatic number for every induced subgraph of G. We prove that a graph is b‐perfect if and only if it does not contain as an induced subgraph a member of a certain list of 22 graphs. This entails the existence of a polynomial‐time recognition algorithm and of a polynomial‐time algorithm for coloring exactly the vertices of every b‐perfect graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:95–122, 2012     

Gallai–Ramsey numbers for cycles

For given graphs G and H and an integer k, the Gallai–Ramsey number is defined to be the minimum integer n such that, in any k coloring of the edges of K_n, there exists a subgraph isomorphic to either a rainbow coloring of G or a monochromatic coloring of H. In this work, we consider Gallai–Ramsey numbers for the case when G=K₃ and H is a cycle of a fixed length.     

On splittable colorings of graphs and hypergraphs

The notion of a split coloring of a complete graph was introduced by Erd?s and Gyárfás [ 7 ] as a generalization of split graphs. In this work, we offer an alternate interpretation by comparing such a coloring to the classical Ramsey coloring problem via a two‐round game played against an adversary. We show that the techniques used and bounds obtained on the extremal (r,m)‐split coloring problem of [ 7 ] are closer in nature to the Turán theory of graphs rather than Ramsey theory. We extend the notion of these colorings to hypergraphs and provide bounds and some exact results. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 226–237, 2002     

<Emphasis Type="Italic">k</Emphasis>-Phase Oscillator Synchronization for Graph Coloring

This paper investigates ways of applying oscillator synchronization to graph coloring. A previous method based on the generalization of the Aihara model is sensitive to the varying degree of the vertices in the graph and there is a strong tendency for the network to form suboptimal limit cycles on regular graphs. Other models such as those by Wu and Nakaguchi, Jin’no and Tanaka do not generalize well into greater than 2-coloring. In this paper, we present ways to overcome these problems and describe the results of our experiments on graphs requiring more than two colors. Our k-phase model enhances the coloring performance over the previous similar models. We further attempt to formalize and analyze the categorical behavior of these systems and discuss connections to other optimization methods.     

Feasible Graphs and Colorings

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring.     

Clique‐coloring some classes of odd‐hole‐free graphs

We consider the problem of clique‐coloring, that is coloring the vertices of a given graph such that no maximal clique of size at least 2 is monocolored. Whereas we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, the existence of a constant C such that any perfect graph is C‐clique‐colorable is an open problem. In this paper we solve this problem for some subclasses of odd‐hole‐free graphs: those that are diamond‐free and those that are bull‐free. We also prove the NP‐completeness of 2‐clique‐coloring K₄‐free perfect graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 233–249, 2006