Search

The traditional graph coloring spectrum allocation algorithm takes into account the efficiency in the different spectrum, but in one allocation period, it can only be assigned one spectrum to the corresponding user. Spectrum allocation algorithm based on maximal independent set can assign a spectrum to multiple users simultaneously and does not constitute interference. However, it does not consider the efficiency in the different spectrum as well as the aggregated interference as it allocates one spectrum to multiple users simultaneously. Based on this, we propose an improved maximal weighted independent set-based graph coloring spectrum allocation algorithm in cognitive radio networks. The algorithm allocates spectrum to the nodes with maximal weighted independent set and fully considers the differences in spectral efficiency and interference spectral differences. The simulation results validates the feasibility of the algorithm, and with the usage of power control technology, it improves the spectrum utilization at the premise of ensuring the received signal to interference plus noise ratio at each intended cognitive radio receivers.

We generalize the model of online computation with three players algorithm, adversary and an oracle called advisor by strengthening the power of the adversary by randomization. In our generalized model, the advisor knows everything about the adversary except the random bits the adversary may use. We examine the expected competitive ratio of online algorithms within this model in order to measure the hardness of online problems in a new way. We start our investigation by proving upper and lower bounds on the competitive ratio for the online graph coloring problem.

A harmonious coloring of a graph is a partitioning of its vertex set into parts such that, there are no edges inside each part, and there is at most one edge between any pair of parts. It is known that finding a minimum harmonious coloring number is NP-hard even in special classes of graphs like trees and split graphs. We initiate a study of parameterized and exact exponential time complexity of harmonious coloring. We consider various parameterizations like by solution size, by above or below known guaranteed bounds and by the vertex cover number of the graph. While the problem has a simple quadratic kernel when parameterized by the solution size, our main result is that the problem is fixed-parameter tractable when parameterized by the size of a vertex cover of the graph. This is shown by reducing the problem to multiple instances of fixed variable integer linear programming. We also observe that it is W[1]-hard to determine whether at most $$n-k$$ or $$\varDelta +1+k$$ colors are sufficient in a harmonious coloring of an n-vertex graph G, where $$\varDelta $$ is the maximum degree of G and k is the parameter. Concerning exact exponential time algorithms, we develop a $$2^{n}n^{\mathcal {O}1}$$ algorithm for finding a minimum harmonious coloring in split graphs improving on the naive $$2^{\mathcal {O}n \log n}$$ algorithm.

Given an n-vertex graph G and two positive integers d,k ∈ ℕ, the (d,kn)-differential coloring problem asks for a coloring of the vertices of G (if one exists) with distinct numbers from 1 to kn (treated as colors), such that the minimum difference between the two colors of any adjacent vertices is at least d. While it was known that the problem of determining whether a general graph is (2,n)-differential colorable is NP-complete, our main contribution is a complete characterization of bipartite, planar and outerplanar graphs that admit (2,n)-differential colorings. For practical reasons, we also consider color ranges larger than n, i.e., k > 1. We show that it is NP-complete to determine whether a graph admits a (3,2n)-differential coloring. The same negative result holds for the (\(\lfloor2n/3\rfloor,2n\))-differential coloring problem, even in the case where the input graph is planar.

We examine the known approximation algorithms for the classic graph coloring problem in general graphs, with the aim to extract and restate the core ideas. We also explore a recent edge-weighted generalization motivated by the modeling of interference in wireless networks. Besides examining the current state-of-the-art and the key open questions, we indicate how results for the classical coloring problem can be transferred to the approximation of general edge-weighted graphs.

We show two results related to the Hamiltonicity and \(k\) -Path algorithms in undirected graphs by Bjorklund [FOCS’10], and Bjorklund et al., [arXiv’10]. First, we demonstrate that the technique used can be generalized to finding some \(k\)-vertex tree with \(l\) leaves in an \(n\)-vertex undirected graph in \(O^*(1.657^k2^{l/2})\) time. It can be applied as a subroutine to solve the \(k\) -Internal Spanning Tree (\(k\)-IST) problem in \(O^*({\text {min}}(3.455^k, 1.946^n))\) time using polynomial space, improving upon previous algorithms for this problem. In particular, for the first time, we break the natural barrier of \(O^*(2^n)\). Second, we show that the iterated random bipartition employed by the algorithm can be improved whenever the host graph admits a vertex coloring with few colors; it can be an ordinary proper vertex coloring, a fractional vertex coloring, or a vector coloring. In effect, we show improved bounds for \(k\) -Path and Hamiltonicity in any graph of maximum degree \(\Delta =4,\ldots ,12\) or with vector chromatic number at most \(8\).

Irregular computations on unstructured data are an important class of problems for parallel programming. Graph coloring is often an important preprocessing step, e.g. as a way to perform dependency analysis for safe parallel execution. The total run time of a coloring algorithm adds to the overall parallel overhead of the application whereas the number of colors used determines the amount of exposed parallelism. A fast and scalable coloring algorithm using as few colors as possible is vital for the overall parallel performance and scalability of many irregular applications that depend upon runtime dependency analysis. Catalyurek et al. have proposed a graph coloring algorithm which relies on speculative, local assignment of colors. In this paper we present an improved version which runs even more optimistically with less thread synchronization and reduced number of conflicts compared to Catalyurek et al.'s algorithm. We show that the new technique scales better on multi-core and many-core systems and performs up to 1.5x faster than its predecessor on graphs with high-degree vertices, while keeping the number of colors at the same near-optimal levels., Comment: To appear in the proceedings of Euro Par 2015

The graph coloring problem is often investigated in the literature. Many insights about many neighboring solutions with the same fitness value are raised but as far as we know, no deep analysis of this neutrality has ever been conducted in the literature. In this paper, we quantify the neutrality of some hard instances of the graph coloring problem. This neutrality property has to be detected as it impacts the search process. Indeed, local optima may belong to plateaus that represents a barrier for local search methods. In this work, we also aim at pointing out the interest of exploiting neutrality during the search. Therefore, a generic local search dedicated to neutral problems, NILS, is performed on several hard instances.

We propose a technique for solving the k-fixed variant of the clique covering problem (k-CCP), where the aim is to determine, whether a graph can be divided into at most k non-overlapping cliques. The approach is based on labeling of the vertices with k available labels and minimizing the number of non-adjacent pairs of vertices with the same label. This is an inverse strategy to k-fixed graph coloring, similar to a tabu search algorithm TabuCol. Thus, we call our method TabuCol-CCP. The technique allowed us to improve the best known results of specialized heuristics for CCP on very large sparse random graphs. Experiments also show a promise in scalability, since a large dense graph does not have to be stored. In addition, we show that Γ function, which is used to evaluate a solution from the neighborhood in graph coloring in $\mathcal{O}(1)$ time, can be used without modification to do the same in k-CCP. For sparse graphs, direct use of Γ allows a significant decrease in space complexity of TabuCol-CCP to $\mathcal{O}(|E|)$, with recalculation of fitness possible with small overhead in $\mathcal{O}(\log \deg(v))$ time, where deg(v) is the degree of the vertex, which is relabeled.

Graph coloring has numerous applications and is a well-known NP-complete problem. The goal of this paper is to survey recent results of the authors on coloring and improper coloring of sparse graphs and to point out some polynomial-time algorithms for coloring (not necessarily optimal) of graphs with bounded maximum average degree.

Greedy embedding (or drawing) is a simple and efficient strategy to route messages in wireless sensor networks. For each source-destination pair of nodes s,t in a greedy embedding there is always a neighbor u of s that is closer to t according to some distance metric. The existence of Euclidean greedy embeddings in ℝ2 is known for certain graph classes such as 3-connected planar graphs. We completely characterize the trees that admit a greedy embedding in ℝ2. This answers a question by Angelini et al. (Graph Drawing 2009) and is a further step in characterizing the graphs that admit Euclidean greedy embeddings.

In this paper we propose a memetic algorithm (MA) for the partition graph coloring problem. Given a clustered graph G = (V,E), the goal is to find a subset V * i¾? V that contains exactly one node for each cluster and a coloring for V * so that in the graph induced by V *, two adjacent nodes have different colors and the total number of used colors is minimal. In our MA we use two distinct solution representations, one for the genetic operators and one for the local search procedure, which are tailored for the corresponding situations, respectively. The algorithm is evaluated on a common benchmark instances set and the computational results show that compared to a state-of-the-art branch and cut algorithm, our MA achieves solid results in very short run-times.

The Graph Coloring Problem (GCP) is a classical NP-complete problem for which several approximate solution algorithms have been proposed: Brelaz algorithm, simulated annealing (SA), ant colony optimization (ACO). This paper reports empirical results on the GCP over a collection of graphs of some approximate solution algorithms. Among them, we test a recently proposed Gravitational Swarm Intelligence (GSI). Results in this benchmarking experiment show that GSI performance compares well to other methods.

We investigate the relationship between two kinds of vertex colorings of hypergraphs: unique-maximum colorings and conflict-free colorings. In a unique-maximum coloring, the colors are ordered, and in every hyperedge of the hypergraph the maximum color in the hyperedge occurs in only one vertex of the hyperedge. In a conflict-free coloring, in every hyperedge of the hypergraph there exists a color in the hyperedge that occurs in only one vertex of the hyperedge. We define corresponding unique-maximum and conflict-free chromatic numbers and investigate their relationship in arbitrary hypergraphs. Then, we concentrate on hypergraphs that are induced by simple paths in tree graphs.

A new algorithm whose name is algorithm of classified order coloring is proposed on the base of the characteristics of the vertex-distinguishing total coloring of complete graph in this paper. All of its elements are classified according to some rules and then are colored in proper sequence. Moreover, a relate-lock-table is presented to judge whether the results are correct. The experimental results show that the algorithm can effectively solve the vertex-distinguishing total coloring of complete graph.

In online graph coloring a graph is revealed to an online algorithm one vertex at a time, and the algorithm must color the vertices as they appear. This paper starts to investigate the advice complexity of this problem --- the amount of oracle information an online algorithm needs in order to make optimal choices. We also consider a more general problem --- a trade-off between online and offline graph coloring. In the paper we prove that precisely ⌈n/2 ⌉−1 bits of advice are needed when the vertices on a path are presented for coloring in arbitrary order. The same holds in the more general case when just a subset of the vertices is colored online. However, the problem turns out to be non-trivial for the case where the online algorithm is guaranteed that the vertices it receives form a subset of a path and are presented in the order in which they lie on the path. For this variant we prove that its advice complexity is βn+O(logn) bits, where β≈0.406 is a fixed constant (we give its closed form). This suggests that the generalized problem will be challenging for more complex graph classes.

We propose a new greedy algorithm for the maximum cardinality matching problem. We give experimental evidence that this algorithm is likely to find a maximum matching in random graphs with constant expected degree c>0, independent of the value of c. This is contrary to the behavior of commonly used greedy matching heuristics which are known to have some range of c where they probably fail to compute a maximum matching.

In the online version of the well-known graph coloring problem, the vertices appear one after the other together with the edges to the already known vertices and have to be irrevocably colored immediately after their appearance. We consider this problem on bipartite, i.e., two-colorable graphs. We prove that 1.13747·log2 n colors are necessary for any deterministic online algorithm to color any bipartite graph on n vertices, thus improving on the previously known lower bound of log2 n + 1 for sufficiently large n.

An acyclic k-coloring of a graph G is a mapping φ from the set of vertices of G to a set of k distinct colors such that no two adjacent vertices receive the same color and φ does not contain any bichromatic cycle. In this paper we prove that every triangulated plane graph with n vertices has a 1-subdivision that is acyclically 3-colorable (respectively, 4-colorable), where the number of division vertices is at most 2n − 5 (respectively, 1.5n − 3.5). On the other hand, we prove an 1.28n (respectively, 0.3n) lower bound on the number of division vertices for acyclic 3-colorings (respectively, 4-colorings) of triangulated planar graphs. Furthermore, we establish the NP-completeness of deciding acyclic 4-colorability for graphs with the maximum degree 5 and for planar graphs with the maximum degree 7.

If a graph G contains no subgraph isomorphic to some graph H, then G is called H-free. A coloring of a graph G = (V,E) is a mapping c: V → {1,2,…} such that no two adjacent vertices have the same color, i.e., c(u) ≠ c(v) if uv ∈ E; if |c(V)| ≤ k then c is a k-coloring. The Coloring problem is to test whether a graph has a coloring with at most k colors for some integer k. The Precoloring Extension problem is to decide whether a partial k-coloring of a graph can be extended to a k-coloring of the whole graph for some integer k. The List Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u). By imposing an upper bound l on the size of each L(u) we obtain the l-List Coloring problem. We first classify the Precoloring Extension problem and the l-List Coloring problem for H-free graphs. We then show that 3-List Coloring is NP-complete for n-vertex graphs of minimum degree n − 2, i.e., for complete graphs minus a matching, whereas List Coloring is fixed-parameter tractable for this graph class when parameterized by the number of vertices of degree n − 2. Finally, for a fixed integer k > 0, the List k -Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u) that must be a subset of {1,…,k}. We show that List 4-Coloring is NP-complete for P 6-free graphs, where P 6 is the path on six vertices. This completes the classification of List k -Coloring for P 6-free graphs.

The graph coloring problem is one of famous combinatorial optimization problems. Some researchers attempted to solve combinatorial optimization problem with evolutionary algorithm, which can find near optimal solution based on the evolution mechanism of the nature. However, it sometimes requires too much cost to evaluate fitness of a large number of individuals in the population when applying the GA to the real world problems. This paper attempts to solve graph coloring problem using a fuzzy clustering based evolutionary approach to reduce the cost of the evaluation. In order to show the feasibility of the method, some experiments with other alternative methods are conducted.

We present new multithreaded vertex ordering and distance-k graph coloring algorithms that are well-suited for multicore platforms. The vertex ordering techniques rely on various notions of "degree", are known to be effective in reducing the number of colors used by a greedy coloring algorithm, and are generic enough to be applicable to contexts other than coloring. We employ approximate degree computation in the ordering algorithms and speculation and iteration in the coloring algorithms as our primary tools for breaking sequentiality and achieving effective parallelization. The algorithms have been implemented using OpenMP, and experiments conducted on Intel Nehalem and other multicore machines using various types of graphs attest that the algorithms provide scalable runtime performance. The number of colors the algorithms use is often close to optimal. The techniques used for computing the ordering and coloring in parallel are applicable to other problems where there is an inherent ordering to the computations that needs to be relaxed for increasing concurrency.

An acyclic coloring of a graph G is a coloring of the vertices of G, where no two adjacent vertices of G receive the same color and no cycle of G is bichromatic. An acyclic k-coloring of G is an acyclic coloring of G using at most k colors. In this paper we prove that any triangulated plane graph G with n vertices has a subdivision that is acyclically 4-colorable, where the number of division vertices is at most 2n−6. We show that it is NP-complete to decide whether a graph with degree at most 7 is acyclically 4-colorable or not. Furthermore, we give some sufficient conditions on the number of division vertices for acyclic 3-coloring of subdivisions of partial k-trees and cubic graphs.

In this paper we initiate a systematic study of a problem that has the flavor of two classical problems, namely Coloring and Domination, from the perspective of algorithms and complexity. A dominator coloring of a graph G is an assignment of colors to the vertices of G such that it is a proper coloring and every vertex dominates all the vertices of at least one color class. The minimum number of colors required for a dominator coloring of G is called the dominator chromatic number of G and is denoted by χd(G). In the Dominator Coloring (DC) problem, a graph G and a positive integer k are given as input and the objective is to check whether χd(G)≤k. We first show that unless P=NP, DC cannot be solved in polynomial time on bipartite, planar, or split graphs. This resolves an open problem posed by Chellali and Maffray [Dominator Colorings in Some Classes of Graphs, Graphs and Combinatorics, 2011] about the polynomial time solvability of DC on chordal graphs. We then complement these hardness results by showing that the problem is fixed parameter tractable (FPT) on chordal graphs and in graphs which exclude a fixed apex graph as a minor.

A coloring of edges of a finite directed graph turns the graph into a finite-state automaton. The synchronizing word of a deterministic automaton is a word in the alphabet of colors (considered as letters) of its edges that maps the automaton to a single state. A coloring of edges of a directed graph of uniform outdegree (constant outdegree of any vertex) is synchronizing if the coloring turns the graph into a deterministic finite automaton possessing a synchronizing word. The road coloring problem is the problem of synchronizing coloring of a directed finite strongly connected graph of uniform outdegree if the greatest common divisor of the lengths of all its cycles is one. The problem posed in 1970 has evoked noticeable interest among the specialists in the theory of graphs, automata, codes, symbolic dynamics as well as among the wide mathematical community. A polynomial time algorithm of O(n3) complexity in the worst case and quadratic in the majority of studied cases for the road coloring of the considered graph is presented below. The work is based on the recent positive solution of the road coloring problem. The algorithm was implemented in the freeware package TESTAS.

How to color 3 colorable graphs with few colors is a problem of longstanding interest. The best polynomial-time algorithm uses n0.2072 colors. There are no indications that coloring using say O(log n) colors is hard. It has been suggested that SDP hierarchies could be used to design algorithms that use ne colors for arbitrarily small e > 0. We explore this possibility in this paper and find some cause for optimism. While the case of general graphs is till open, we can analyse the Lasserre relaxation for two interesting families of graphs. For graphs with low threshold rank (a class of graphs identified in the recent paper of Arora, Barak and Steurer on the unique games problem), Lasserre relaxations can be used to find an independent set of size Ω(n) (i.e., progress towards a coloring with O(log n) colors) in nO(D) time, where D is the threshold rank of the graph. This algorithm is inspired by recent work of Barak, Raghavendra, and Steurer on using Lasserre Hierarchy for unique games. The algorithm can also be used to show that known integrality gap instances for SDP relaxations like strict vector chromatic number cannot survive a few rounds of Lasserre lifting, which also seems reason for optimism. For distance transitive graphs of diameter Δ, we can show how to color them using O(log n) colors in n2O(Δ) time. This family is interesting because the family of graphs of diameter O(1/e) is easily seen to be complete for coloring with ne colors. The distance-transitive property implies that the graph "looks" the same in all neighborhoods. The full version of this paper can be found at: http://www.cs.princeton.edu/~rongge/LasserreColoring.pdf .

In the INTERVALIZING COLOURED GRAPHS problem, one must decide for a given graph G = (V,E) with a proper vertex coloring of G whether G is the subgraph of a properly colored interval graph. For the case that the number of colors k is fixed, we give an exact algorithm that uses O*(2n/log1-e(n)) time for all e > 0. We also give an O*(2n) algorithm for the case that the number of colors k is not fixed.

We introduce a new nature inspired algorithm to solve the Graph Coloring Problem (GCP): the Gravitational Swarm. The Swarm is composed of agents that act individually, but that can solve complex computational problems when viewed as a whole. We formulate the agent’s behavior to solve the GCP. Agents move as particles in the gravitational field defined by some target objects corresponding to graph node colors. Knowledge of the graph to be colored is encoded in the agents as friend-or-foe information. We discuss the convergence of the algorithm and test it over well-known benchmarking graphs, achieving good results in a reasonable time.

Graph coloring has been applied in a variety of applications, but not for data hiding. Therefore, in this paper, we are proposing two graph coloring-based data hiding schemes that embed secret data in spatial domain of gray scale images. The main idea of our schemes is to use a graph, in which every vertex corresponds to a pixel pair, to hide data by replacing a pair of pixels of one color with a pair of pixels of a different color, with every color corresponding to some bits of the secret message. The performance of the proposed schemes has been evaluated by a joint evaluation of the imperceptibility of the images they produce and their embedding capacity. Also, the validity of the proposed schemes has been proven by comparing them with some other schemes.

Register allocation is one of most important compiler optimization techniques. The most famous method for register allocation is graph coloring and the solution presented in this paper (RAGCES) is based on the graph coloring too; for coloring interference graph, evolutionary algorithm is used. In this method graph coloring and selecting variables for spilling is taken place at the same time. This method was tested on several graphs and results were compared with the results of the previous methods.

The best known method for determining lower bounds on the vertex coloring number of a graph is the linear-programming columngeneration technique first employed by Mehrotra and Trick in 1996. We present an implementation of the method that provides numerically safe results, independent of the floating-point accuracy of linear-programming software. Our work includes an improved branch-and-bound algorithm for maximum-weight stable sets and a parallel branch-and-price framework for graph coloring. Computational results are presented on a collection of standard test instances, including the unsolved challenge problems created by David S. Johnson in 1989.

In this paper, we generalize the greedy routing concept to use semimetric spaces. We prove that any connected n-vertex graph G admits a greedy embedding onto an appropriate semi-metric space such that (1) each vertex v of the graph is represented by up to k virtual coordinates (where the numbers are from 1 to 2n - 1 and k - deg(v)); and (2) using an appropriate distance definition, there is always a distance decreasing path between any two vertices in G. In particular, we prove that, for a 3-connected plane graph G, there is a greedy embedding of G such that: (1) the greedy embedding can be obtained in linear time; and (2) each vertex can be represented by at most 3 virtual coordinates from 1 to 2n - 1. To our best knowledge, this is the first greedy routing algorithm for 3-connected plane graphs, albeit with non-standard notions of greedy embedding and greedy routing, such that: (1) it runs in linear time to compute the virtual coordinates for the vertices; and (2) the virtual coordinates are represented succinctly in O(logn) bits.

We study methods of planarizing and acyclically coloring claw-free subcubic graphs. We give a polynomial-time algorithm that, given such a graph G, produces an independent set Q of at most n/6 vertices whose removal from G leaves an induced planar subgraph P (in fact, P has treewidth at most four). We further show the stronger result that in polynomial-time a set of at most n/6 edges can be identified whose removal leaves a planar subgraph (of treewidth at most four). From an approximability point of view, we show that our results imply 6/5- and 9/8-approximation algorithms, respectively, for the (NP-hard) problems of finding a maximum induced planar subgraph and a maximum planar subgraph of a subcubic claw-free graph, respectively. Regarding acyclic colorings, we give a polynomial-time algorithm that finds an optimal acyclic vertex coloring of a subcubic claw-free graph. To our knowledge, this represents the largest known subclass of subcubic graphs such that an optimal acyclic vertex coloring can be found in polynomial-time. We show that this bound is tight by proving that the problem is NP-hard for cubic line graphs (and therefore, claw-free graphs) of maximum degree d≥4. An interesting corollary to the algorithm that we present is that there are exactly three subcubic claw-free graphs that require four colors to be acyclically colored. For all other such graphs, three colors suffice.

We study the maximum differential graph coloring problem, in which the goal is to find a vertex labeling for a given undirected graph that maximizes the label difference along the edges. This problem has its origin in map coloring, where not all countries are necessarily contiguous. We define the differential chromatic number and establish the equivalence of the maximum differential coloring problem to that of k-Hamiltonian path. As computing the maximum differential coloring is NP-Complete, we describe an exact backtracking algorithm and a spectral-based heuristic. We also discuss lower bounds and upper bounds for the differential chromatic number for several classes of graphs.

In this paper, we investigate heuristics in order to solve the Approximated Matching Problem (AGM). We propose a tabu search algorithm which exploits a simple neighborhood but is initialized by a greedy procedure which uses a measure of similarity between the vertices of the two graphs. The algorithm is tested on a large collection of graphs of various sizes (from 300 vertices and up to 3000 vertices) and densities. Computing times range from less than 1 second up to a few minutes. The algorithm obtains consistently very good results, especially on labeled graphs. The results obtained by the tabu algorithm alone (without the greedy procedure) were very poor, illustrating the importance of using vertex similarity during the early steps of the search process.

We consider the problem of coloring edges of a graph subject to the following constraint: for every vertex v, all the edges incident to v have to be colored with at most q colors. The goal is to find a coloring satisfying the above constraint and using the maximum number of colors.

This paper proposes an approach toward improving re-coloring based clustering with graph b-coloring. Previous b-coloring based clustering algorithm did not consider the quality of clusters. Although a greedy re-coloring algorithm was proposed, it was still restrictive in terms of the explored search space due to its greedy and sequential re-coloring process. We aim at overcoming the limitations by enlarging the search space for re-coloring, while guaranteeing b-coloring properties. A best first re-coloring algorithm is proposed to realize nongreedy search for the admissible colors of vertices. A color exchange algorithm is proposed to remedy the problem in sequential re-coloring. These algorithms are orthogonal with respect to the re-colored vertices and thus can be utilized in conjunction. Preliminary evaluations are conducted over several benchmark datasets, and the results are encouraging.

We present the discrete beeping communication model, which assumes nodes have minimal knowledge about their environment and severely limited communication capabilities. Specifically, nodes have no information regarding the local or global structure of the network, do not have access to synchronized clocks and are woken up by an adversary. Moreover, instead on communicating through messages they rely solely on carrier sensing to exchange information. This model is interesting from a practical point of view, because it is possible to implement it (or emulate it) even in extremely restricted radio network environments. From a theory point of view, it shows that complex problems (such as vertex coloring) can be solved efficiently even without strong assumptions on properties of the communication model. We study the problem of interval coloring, a variant of vertex coloring specially suited for the studied beeping model. Given a set of resources, the goal of interval coloring is to assign every node a large contiguous fraction of the resources, such that neighboring nodes have disjoint resources. A k-interval coloring is one where every node gets at least a 1/k fraction of the resources. To highlight the importance of the discreteness of the model, we contrast it against a continuous variant described in [17]. We present an O(1) time algorithm that with probability 1 produces a O(Δ)-interval coloring. This improves an O(log n) time algorithm with the same guarantees presented in [17], and accentuates the unrealistic assumptions of the continuous model. Under the more realistic discrete model, we present a Las Vegas algorithm that solves O(Δ)- interval coloring in O(log n) time with high probability and describe how to adapt the algorithm for dynamic networks where nodes may join or leave. For constant degree graphs we prove a lower bound of Ω(log n) on the time required to solve interval coloring for this model against randomized algorithms. This lower bound implies that our algorithm is asymptotically optimal for constant degree graphs.

In this paper we consider two problems: the edge coloring and the strong edge coloring problems on unit disk graphs (UDGs). Both problems have important applications in wireless sensor networks as they can be used to model link scheduling problems in such networks. It is well known that both problems are NP-complete, and approximation algorithms for them have been extensively studied under the centralized model of computation. Centralized algorithms, however, are not suitable for ad-hoc wireless sensor networks whose devices typically have limited resources, and lack the centralized coordination. We develop local distributed approximation algorithms for the edge coloring and the strong edge coloring problems on unit disk graphs. For the edge coloring problem, our local distributed algorithm has approximation ratio 2 and locality 50. We show that the locality upper bound can be improved to 28 while keeping the same approximation ratio, at the expense of increasing the computation time at each node. For the strong edge coloring problem on UDGs, we present two local distributed algorithms with different tradeoffs between their approximation ratio and locality. The first algorithm has ratio 128 and locality 22, whereas the second algorithm has ratio 10 and locality 180.

In this paper we study an interesting class of graph parameters. These parameters arise both from edge coloring models and from limits of vertex coloring models with a fixed number of vertices. Their vertex connection matrices have exponentially bounded rank growth.

High Degree Graphs Contain Large-Star Factors.- Iterated Triangle Partitions.- PageRank and Random Walks on Graphs.- Solution of Peter Winkler's Pizza Problem*+.- Tight Bounds for Embedding Bounded Degree Trees.- Betti Numbers are Testable*.- Rigid and Globally Rigid Graphs with Pinned Vertices.- Noise Sensitivity and Chaos in Social Choice Theory.- Coloring Uniform Hypergraphs with Small Edge Degrees.- Extremal Graphs and Multigraphs with Two Weighted Colours.- Regularity Lemmas for Graphs.- Edge Coloring Models as Singular Vertex Coloring Models.- List Total Weighting of Graphs.- Open Problems.

Deleting a minimum number of vertices from a graph to obtain a proper interval graph is an NP-complete problem. At WG 2010 van Bevern et al. gave an O((14k + 14) k + 1 kn 6) time algorithm by combining iterative compression, branching, and a greedy algorithm. We show that there exists a simple greedy O(n + m) time algorithm that solves the Proper Interval Vertex Deletion problem on \(\{claw,net,\allowbreak tent,\allowbreak C_4,C_5,C_6\}\)-free graphs. Combining this with branching on the forbidden structures \(claw,net,tent,\allowbreak C_4,C_5,\) and C 6 enables us to get an O(kn 6 6 k ) time algorithm for Proper Interval Vertex Deletion, where k is the number of deleted vertices.

Given a finite directed graph, a coloring of its edges turns the graph into a finite-state automaton. A k-synchronizing word of a deterministic automaton is a word in the alphabet of colors at its edges that maps the state set of the automaton at least on k-element subset. A coloring of edges of a directed strongly connected finite graph of a uniform outdegree (constant outdegree of any vertex) is k-synchronizing if the coloring turns the graph into a deterministic finite automaton possessing a k-synchronizing word. For k=1 one has the well known road coloring problem. The recent positive solution of the road coloring problem implies an elegant generalization considered first by Beal and Perrin: a directed finite strongly connected graph of uniform outdegree is k-synchronizing iff the greatest common divisor of lengths of all its cycles is k. Some consequences for coloring of an arbitrary finite digraph are presented. We describe a subquadratic algorithm of the road coloring for the k-synchronization implemented in the package TESTAS. A new linear visualization program demonstrates the obtained coloring. Some consequences for coloring of an arbitrary finite digraph and of such a graph of uniform outdegree are presented.

Hybridizations of evolutionary algorithms and local search are among the best-performing algorithms for vertex coloring. However, the theoretical knowledge about these algorithms is very limited and it is agreed that a solid theoretical foundation is needed. We consider an iterated local search algorithm that iteratively tries to improve a coloring by applying mutation followed by local search. We investigate the capabilities and the limitations of this approach using bounds on the expected number of iterations until an optimal or near-optimal coloring is found. This is done for two different mutation operators and for different graph classes: bipartite graphs, sparse random graphs, and planar graphs.

We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of roughly 0.842 and runs in O(n3m) time, where n (respectively, m) is the number of vertices (respectively, edges) in the input graph. The previously best ratio achieved by a polynomial-time approximation algorithm was 5/6 ≈ 0.833.

We investigate a coloring problem, called ordered coloring, in grids and some other families of grid-like graphs. Ordered coloring (also known as vertex ranking) is related to conflict-free coloring and other traditional coloring problems. Such coloring problems can model (among others) efficient frequency assignments in cellular networks. Our main technical results improve upper and lower bounds for the ordered chromatic number of grids and related graphs. To the best of our knowledge, this is the first attempt to calculate exactly the ordered chromatic number of these graph families.

Incrementally k-list coloring a graph means that a graph is given by adding stepwise one vertex after another, and for each intermediate step we ask for a vertex coloring such that each vertex has one of the colors specified by its associated list containing some of in total k colors We introduce the “conservative version” of this problem by adding a further parameter c∈ℕ specifying the maximum number of vertices to be recolored between two subsequent graphs (differing by one vertex) This “conservation parameter” c models the natural quest for a modest evolution of the coloring in the course of the incremental process instead of performing radical changes We show that the problem is NP-hard for k≥3 and W[1]-hard when parameterized by c In contrast, the problem becomes fixed-parameter tractable with respect to the combined parameter (k,c) We prove that the problem has an exponential-size kernel with respect to (k,c) and there is no polynomial-size kernel unless NP⊆coNP/poly Finally, we provide empirical findings for the practical relevance of our approach in terms of an effective graph coloring heuristic.