Search

Given a graph G = (V , E) with n = | V | vertices, the graph coloring problem is defined as Find a color vector C = (c (v)) , where c (v) ∈ { 1 , 2 , ... , n } denotes the color of vertex v ∈ V , such that no monochromatic edge exists in G and the span , the total number of distinct colors in C , is minimized. Since the problem is NP-complete, a greedy coloring is commonly used for solving it. Greedy coloring visits the vertices of G following an order S , and while visiting a vertex v , it puts the minimum color absent in all neighbors of v. We show that the orders producing span ≤ k , where k ≤ n is a positive integer, can be partitioned into disjoint subsets of equivalent orders. Next, we propose a selective search (SS) algorithm, which takes ρ as an input parameter, selects ≥ ρ orders each from a different set of equivalent orders with high probability, applies greedy coloring on them, and returns the color vector with minimum span. We analytically show that SS performs better than greedy coloring with high probability by evaluating the same number of orders. We propose an incremental search heuristic (ISH), which ρ 1 times execute SS with parameter ρ 2 and returns the color vector with minimum span. A parallel version of ISH called PISH is also proposed, executing ρ 1 SS calls in parallel. We show that ISH hits an optimum coloring for a graph G = (V , E) with χ (G) (Δ (G) + 1) ≤ n e in expected O (| V | + | E |) time and space complexities. We have evaluated ISH and PISH on 136 challenging benchmarks and shown that they significantly outperform 10 existing state-of-the-art algorithms. Finally, we validated our theoretical findings by evaluating ISH and greedy coloring on random graphs. [ABSTRACT FROM AUTHOR]

Bandwidth consecutive multicoloring problem is also known as a b-coloring problem. Let G = (V, E) be a graph where V is the set of vertices and E is the set of edges. Let each vertex v of V has a positive integer weight b (v) and each edge (v, w) of E has a non-negative integer weight b (v, w). A bandwidth consecutive multicoloring of a graph is a problem of assigning b (v) consecutive positive integers to each vertex v of V in such a manner that the difference between all the integers of vertex v and all the integers of vertex w is greater than b (v, w). The maximum integer assigned in this coloring is called the span of the coloring. The b-coloring is the problem of minimizing this span. No metaheuristic is proposed for general graphs so far for this problem till date as it is strongly NP-hard. In this paper, we proposed three heuristics for the problem including a greedy randomized adaptive search procedure (GRASP). The efficiency of these algorithms is tested on benchmark graphs and their performance is compared among themselves. Experimental results showed that among all three proposed heuristics, GRASP performed well for the given problem. [ABSTRACT FROM AUTHOR]

The maximum clique problems calls for determining the size of the largest clique in a given graph. This graph problem affords a number of zero-one linear programming formulations. In this case study we deal with some of these formulations. We consider ways for tightening the formulations. We carry out numerical experiments to see the improvements the tightened formulations provide. [ABSTRACT FROM AUTHOR]

In this paper, we explore proper vertex colorings of graphs with the additional constraint that the colors used on the closed neighborhood of every vertex form an integer interval; such colorings are called proper closed interval vertex colorings (PCIV colorings for short). As not every graph admits such a coloring, we are concerned with the problem of deciding which graphs admit PCIV colorings, describing several sufficient conditions (among them unique and 3-colorability, partial decomposability into two bipartite graphs, and density constraints) as well as some constructions of PCIV uncolorable graphs. We also present an algorithmic support for PCIV colorability based on a modification of the standard greedy algorithm for standard proper coloring. • Propose a new proper coloring (PCIV coloring) where colors on closed neighborhoods of vertices form integer intervals. • Particular sufficient conditions for PCIV colorability are proved. • Several constructions of PCIV uncolorable graphs are presented. • Greedy algorithm for finding a PCIV coloring is developed. [ABSTRACT FROM AUTHOR]

Copyright of Informatica (03505596) is the property of Slovene Society Informatika and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

It is a common practice to find upper bound for clique number via legal coloring of the nodes of the graph. We will point out that with a little extra work we may lower this bound. Applying this procedure to a suitably constructed auxiliary graph one may further improve the clique size estimate of the original graph.

We will describe an algorithm to establish an upper estimate of the clique number of a given graph. The procedure is based on greedy legal coloring of the nodes. In order to assess the performance of the procedure we carried out a large scale numerical experiment. [ABSTRACT FROM AUTHOR]

A connected ordering (v 1 , v 2 , ... , v n) of V (G) is an ordering of the vertices such that v i has at least one neighbor in { v 1 , ... , v i − 1 } for every i ∈ { 2 , ... , n }. A connected greedy coloring (CGC for short) is a coloring obtained by applying the greedy algorithm to a connected ordering. This has been first introduced in 1989 by Hertz and de Werra, but still very little is known about this problem. An interesting aspect is that, contrary to the traditional greedy coloring, it is not always true that a graph has a connected ordering that produces an optimal coloring; this motivates the definition of the connected chromatic number of G , which is the smallest value χ c (G) such that there exists a CGC of G with χ c (G) colors. An even more interesting fact is that χ c (G) ≤ χ (G) + 1 for every graph G (Benevides et al. 2014). In this paper, in the light of the dichotomy for the coloring problem restricted to H -free graphs given by Král' et al. in 2001, we are interested in investigating the problems of, given an H -free graph G : (1). deciding whether χ c (G) = χ (G) ; and (2). given also a positive integer k , deciding whether χ c (G) ≤ k. We denote by P t the path on t vertices, and by P t + K 1 the union of P t and a single vertex. We have proved that Problem (2) has the same dichotomy as the coloring problem (namely, it is polynomial when H is an induced subgraph of P 4 or of P 3 + K 1 , and it is NP -complete otherwise). As for Problem (1), we have proved that χ c (G) = χ (G) always hold when H is an induced subgraph of P 5 or of P 4 + K 1 , and that it is NP -complete to decide whether χ c (G) = χ (G) when H is not a linear forest or contains an induced P 9. We mention that some of the results involve fixed k and fixed χ (G). [ABSTRACT FROM AUTHOR]

One method to obtain a proper vertex coloring of graphs using a reasonable number of colors is to start from any arbitrary proper coloring and then repeat some local re-coloring techniques to reduce the number of color classes. The Grundy (First-Fit) coloring and color-dominating colorings of graphs are two well-known such techniques. The color-dominating colorings are also known and commonly referred as b-colorings. But these two topics have been studied separately in graph theory. We introduce a new coloring procedure which combines the strategies of these two techniques and satisfies an additional property. We first prove that the vertices of every graph G can be effectively colored using color classes say C 1 , ... , C k such that (i) for any two colors i and j with 1 ≤ i < j ≤ k , any vertex of color j is adjacent to a vertex of color i, (ii) there exists a set { u 1 , ... , u k } of vertices of G such that u j ∈ C j for any j ∈ { 1 , ... , k } and u k is adjacent to u j for each 1 ≤ j ≤ k with j ≠ k , and (iii) for each i and j with i ≠ j , the vertex u j has a neighbor in C i . This provides a new vertex coloring heuristic which improves both Grundy and color-dominating colorings. Denote by z(G) the maximum number of colors used in any proper vertex coloring satisfying the above properties. The z(G) quantifies the worst-case behavior of the heuristic. We prove the existence of { G n } n ≥ 1 such that min { Γ (G n) , b (G n) } → ∞ but z (G n) ≤ 3 for each n. For each positive integer t we construct a family of finitely many colored graphs D t satisfying the property that if z (G) ≥ t for a graph G then G contains an element from D t as a colored subgraph. This provides an algorithmic method for proving numeric upper bounds for z(G). [ABSTRACT FROM AUTHOR]

In this paper, we answer a long-standing open question proposed by Bodlaender in 1991: the game chromatic number is PSPACE-hard. We also prove that the game Grundy number is PSPACE-hard. In fact, we prove that both problems (the graph coloring game and the greedy coloring game) are PSPACE-Complete even if the number of colors is the chromatic number. Despite this, we prove that the game Grundy number is equal to the chromatic number for split graphs and several superclasses of cographs, extending a result of Havet and Zhu in 2013. [ABSTRACT FROM AUTHOR]

To carry out a clique search in a given graph in a parallel fashion, one divides the problem into a very large number of smaller instances. To sort out as many resulted smaller problems as possible, one can rely on upper estimates of the clique sizes. Legal coloring of the nodes of the graphs is a commonly used tool to establish upper bound of the clique size. We will point out that coloring of the nodes can also be used to divide the clique search problem into smaller ones. We will introduce a non-conventional coloring of the edges of the given graph. We will gather theoretical and computational evidence that the proposed edge coloring provides better estimates for the clique size than the node coloring and can be used to divide the original problem into subproblems. [ABSTRACT FROM AUTHOR]

We show that depth first search can be used to give a proper coloring of connected signed graphs G using at most $$\Delta (G)$$ colors, provided G is different from a balanced complete graph, a balanced cycle of odd length, and an unbalanced cycle of even length, thus giving a new, short proof to the generalization of Brooks' theorem to signed graphs, first proved by Máčajová, Raspaud, and Škoviera. [ABSTRACT FROM AUTHOR]

Abstract: Given a graph , a greedy coloring of is a proper coloring such that, for each two colors , every vertex of colored has a neighbor colored . The Grundy number is the maximum number of colors in a greedy coloring of . Zaker (2006) proved that determining the Grundy number is NP-hard even for complements of bipartite graphs. A -coloring of is a proper coloring such that every color class contains a vertex which is adjacent to at least one vertex in every other color class. The -chromatic number is the maximum number of colors in a -coloring of . Irving and Manlove (1999) proved that determining the -chromatic number is NP-hard. In this paper, we obtain polynomial time algorithms to determine the Grundy number and the -chromatic number of -graphs, for every fixed , which are the graphs such that every set of at most vertices induces at most distinct . These algorithms are fixed parameter tractable on the parameter , where is the minimum such that is a -graph. [Copyright &y& Elsevier]

Dynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In the dynamic setting of the problem, a graph we color is not given in advance and new vertices together with adjacent edges are revealed one after another at algorithm's input during the coloring process. Moreover, independently of the algorithm, some vertices may lose their colors and the algorithm may be asked to color them again. We formally define a dynamic graph coloring problem, the dynamic chromatic number and prove various bounds on its value. We also analyze the effectiveness of the dynamic coloring algorithm Dynamic-Fit for selected classes of graphs. In particular, we deal with trees, products of graphs and classes of graphs for which Dynamic-Fit is competitive. Motivated by applications, we state the problem of dynamic coloring with discoloring constraints for which the performance of the dynamic algorithm Time-Fit is analyzed and give a characterization of graphs k-critical for Time-Fit. Since for any fixed k > 0 the number of such graphs is finite, it is possible to decide in polynomial time whether Time-Fit will always color a given graph with at most k colors. [ABSTRACT FROM AUTHOR]

The first-fit chromatic number of a graph is the number of colors needed in the worst case of a greedy coloring. It is also called the Grundy number, which is defined to be the maximum number of classes in an ordered partition of the vertex set of a graph G into independent sets V1, V2, … , Vk so that for each 1 ≤ i < j ≤ k and for each x ϵ Vi there exists a y ϵ Vi such that x and y are adjacent. In this paper, we study the first-fit chromatic number of outerplanar and planar graphs as well as Cartesian products of graphs, and in particular we give asymptotically tight results for outerplanar graphs. [ABSTRACT FROM AUTHOR]

Abstract: Greedy algorithm sometimes uses more than colors while coloring a graph G. A greedy defining set is an object to eliminate these extra colors so that the greedy coloring results in a minimum coloring of an order graph G. In this note we report some of the previous results as well as new results on greedy defining sets of graphs and Latin squares. [Copyright &y& Elsevier]

Abstract: It is a well-known proposition that every graph of chromatic number larger than contains every tree with edges. The ‘standard’ reasoning is that such a graph must contain a subgraph of minimum degree at least . Bohman, Frieze, and Mubayi noticed that, although this argument does not work for hypergraphs, it is still possible that the proposition holds for hypergraphs as well. Indeed, Loh recently proved that every uniform hypergraph of chromatic number larger than contains every hypertree with edges. Here we observe that the basic property of the well-known greedy algorithm immediately implies a much more general result (with a conceptually simpler proof): if the greedy algorithm colors the vertices of an -uniform hypergraph with more than colors then the hypergraph contains every -uniform hypertree with edges. [ABSTRACT FROM AUTHOR]