Search

This study focuses on two heuristic algorithms for the graph vertex coloring problem: the sequential (greedy) coloring algorithm (SCA) and the Welsh–Powell algorithm (WPA). The code of the algorithms is presented and discussed. The methodology and conditions of the experiments are presented. The execution time of the algorithms was calculated as the average of four different starts of the algorithms for all analyzed graphs, taking into consideration the multitasking mode of the operating system. In the graphs with less than 600 vertices, in 90% of cases, both algorithms generated the same solutions. In only 10% of cases, the WPA algorithm generates better solutions. However, in the graphs with more than 1,000 vertices, in 35% of cases, the WPA algorithm generates better solutions. The results show that the difference in the execution time of the algorithms for all graphs is acceptable, but the quality of the solutions generated by the WPA algorithm in more than 20% of cases is better compared to the SC algorithm. The results also show that the quality of the solutions is not related to the number of iterations performed by the algorithms.

The communication capacity control of the computer wireless network is the basis for realizing the efficient communication of massive data. In order to study the communication capacity control technology of the computer wireless network, improve the control effect of a large amount of data communication, and calculate the capacity of the wireless network in real time, this paper uses the fuzzy wavelet neural network to predict the wireless network channel. After the interference-free channel is obtained, the load balancing strategy of the ant colony optimization algorithm is used to filter the channel, and the channel allocation sequence with the most balanced load distribution is obtained, and a priority selection list is generated. After discretizing the channels in the largest discretization selection list, the channel sequence is allocated to the pair of nodes with communication requests according to the greedy coloring algorithm, so as to realize the communication capacity control of the computer wireless network. The test results show that the technology can guarantee good communication performance in both static and dynamic networks and can effectively complete network communication of massive data, and the communication capacity control effect is good.

Unmanned aerial vehicles (UAVs) facilitate information collection greatly in the Internet-of-Things (IoT) systems due to their superior flexibility and mobility. On the other hand, nonorthogonal multiple access (NOMA) is regarded as a promising technology to provide high spectral efficiency and support massive connectivity in fifth-generation networks. The integration of NOMA into UAV-assisted wireless networks shows great potential, but how to determine the user grouping and power allocation in NOMA according to the high mobility of UAV is challenging. In this article, we propose a general NOMA-enabled UAV-assisted data collection (NUDC) protocol to maximize the sum rate of a wireless sensor network (WSN), where the location of UAV, sensor grouping, and power control are jointly considered. Moreover, a joint signal-to-interference ratio (SIR) hypergraph-based grouping and power control (SHG-PC) NOMA scheme is provided to obtain the appropriate sensor grouping and the optimal power control solutions efficiently, in which the hypergraph and the greedy coloring algorithm are exploited to find out the optimized group relationships. Extensive simulation results demonstrate the efficiency of our proposed protocol.

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 Kral’ 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 ) .

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.

Device-to-Device (D2D) is a very promising technology which can significantly improved the spectral efficiency, while the communication distance is often limited by resource constraints. The reconfigurable intelligent surface (RIS) can optimize the passive phase shift of each element to enhance the signal strength at D2D devices and expand the communication coverage. Regardless of the above advantages, the RIS-aided D2D communication will introduce severe interference to user equipments (UE) or D2D device itself with irrational resource allocation schemes. In this paper, based on hypergraph-with-weight model, a RIS-aided D2D communication network is constructed where the weight of each hyperedge represents the interference severity. Moreover, A greedy coloring algorithm is proposed to solve the complex resource allocation problem in a simple and effective manner. Simulation results show that the proposed greedy coloring algorithm can greatly reduce interference and improve network capacity.

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 several superclasses of cographs, extending a result of Havet and Zhu in 2013.

In this paper, we study the achromatic and the pseudoachromatic numbers of planar and outerplanar graphs as well as planar graphs of girth 4 and graphs embedded on a surface. We give asymptotically tight results and lower bounds for maximal embedded graphs., 19 pages, 11 figures

Graph coloring has a wide range of real world applications, such as in the operations research, communication network, computational biology and compiler optimization fields. In our recent work [1], we propose a divide-and-conquer approach for graph coloring, called VColor. Such an approach has three generic subroutines. (i) Graph partition subroutine: VColor partitions a graph G into a vertex cut partition (VP), which comprises a vertex cut component (VCC) and small non-overlapping connected components (CCs). (ii) Component coloring subroutine: VColor colors the VCC and the CCs by efficient algorithms. (iii) Color combination subroutine: VColor combines the local colors by exploiting the maximum matchings of color combination bigraphs (CCBs). VColor has revealed some major bottlenecks of efficiency in these subroutines. Therefore, in this paper, we propose VColor*, an approach which addresses these efficiency bottlenecks without using more colors both theoretically and experimentally. The technical novelties of this paper are the following. (i) We propose the augmented VP to index the crossing edges of the VCC and the CCs and propose an optimized CCB construction algorithm. (ii) For sparse CCs, we propose using a greedy coloring algorithm that is of polynomial time complexity in the worst case, while preserving the approximation ratio. (iii) We propose a distributed graph coloring algorithm. Our extensive experimental evaluation on real-world graphs confirms the efficiency of VColor*. In particular, VColor* is 20X and 50X faster than VColor and uses the same number of colors with VColor on the Pokec and PA datasets, respectively. VColor* also significantly outperforms the state-of-the-art graph coloring methods.

In this paper we consider colorings of oriented graphs, i.e. digraphs without cycles of length 2. Given some oriented graph $G=(V,E)$, an oriented $r$-coloring for $G$ is a partition of the vertex set $V$ into $r$ independent sets, such that all the arcs between two of these sets have the same direction. The oriented chromatic number of $G$ is the smallest integer $r$ such that $G$ permits an oriented $r$-coloring. In this paper we consider the Oriented Chromatic Number problem on classes of recursively defined oriented graphs. Oriented co-graphs (short for oriented complement reducible graphs) can be recursively defined defined from the single vertex graph by applying the disjoint union and order composition. This recursive structure allows to compute an optimal oriented coloring and the oriented chromatic number in linear time. We generalize this result using the concept of perfect orderable graphs. Therefore, we show that for acyclic transitive digraphs every greedy coloring along a topological ordering leads to an optimal oriented coloring. Msp-digraphs (short for minimal series-parallel digraphs) can be defined from the single vertex graph by applying the parallel composition and series composition. We prove an upper bound of $7$ for the oriented chromatic number for msp-digraphs and we give an example to show that this is bound best possible. We apply this bound and the recursive structure of msp-digraphs to obtain a linear time solution for computing the oriented chromatic number of msp-digraphs. In order to generalize the results on computing the oriented chromatic number of special graph classes, we consider the parameterized complexity of the Oriented Chromatic Number problem by so-called structural parameters, which are measuring the difficulty of decomposing a graph into a special tree-structure, 25 pages. arXiv admin note: text overlap with arXiv:2006.13911

Graph coloring is one of the fundamentally known NP-complete problem. Several heuristics have been developed to solve this problem, among which greedy coloring is the most naturally used one. In greedy coloring, vertices are traversed following an order and hence performance of it highly depends on finding a good order. In this paper, we propose an incremental search heuristic (ISH) which considers some ρ1 random orders and for each of them it calls a selective search (SS) procedure with parameter ρ2. Given an order, SS considers only those orders which produces equal or less number of distinct colors than a given order. We showed that those orders can be partitioned into disjoint subsets of equivalent orders. To make effective search, SS selects and evaluates only one order from such a subset. Analytically we have shown that ISH can solve the graph coloring instances on sparse graph in expected polynomial time. Through simulations, we have evaluated ISH on 86 challenging benchmarks and compare results with state of the art existing algorithms. We observed that ISH significantly outperforms existing algorithms specially for sparse graphs and also produces reasonably good results for others.

Post-print (lokagerð höfundar), We give a distributed (1+eps)-approximation algorithm for the minimum vertex coloring problem on interval graphs, which runs in the LOCAL model and operates in O((1/eps) log* n) rounds. If nodes are aware of their interval representations, then the algorithm can be adapted to the CONGEST model using the same number of rounds. Prior to this work, only constant factor approximations using O(log* n) rounds were known. Linial's ring coloring lower bound implies that the dependency on log* n cannot be improved. We further prove that the dependency on 1/eps is also optimal. To obtain our CONGEST model algorithm, we develop a color rotation technique that may be of independent interest. We demonstrate that color rotations can also be applied to obtain a (1+eps)-approximate multicoloring of directed trees in O((1/eps)log* n) rounds., Magnus M. Halldorsson is supported by grants 152679-05 and 174484-05 from the Icelandic Research Fund. Christian Konrad is supported by the Centre for Discrete Mathematics and its Applications (DIMAP) at Warwick University and by EPSRC award EP/N011163/1., "Peer Reviewed"

Very recently, a long-standing open question proposed by Bodlaender in 1991 was answered: the graph coloring game is PSPACE-complete. In 2019, Andres and Lock proposed five variants of the graph coloring game and left open the question of PSPACE-hardness related to them. In this paper, we prove that these variants are PSPACE-complete for the graph coloring game and also for the greedy coloring game, even if the number of colors is the chromatic number. Finally, we also prove that a connected version of the graph coloring game, proposed by Charpentier et al. in 2019, is PSPACE-complete.

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.

An unexpected difference between online and offline algorithms is observed. The natural greedy algorithms are shown to be worst case online optimal for Online Independent Set and Online Vertex Cover on graphs with “enough” isolated vertices, Freckle Graphs. For Online Dominating Set , the greedy algorithm is shown to be worst case online optimal on graphs with at least one isolated vertex. These algorithms are not online optimal in general. The online optimality results for these greedy algorithms imply optimality according to various worst case performance measures, such as the competitive ratio. It is also shown that, despite this worst case optimality, there are Freckle graphs where the greedy independent set algorithm is objectively less good than another algorithm. It is shown that it is NP -hard to determine any of the following for a given graph: the online independence number, the online vertex cover number, and the online domination number.

Given a graph G = ( V , E ) , a coloring function χ : V → C , assigning each vertex a color, is called convex if, for every color c ∈ C , the set of vertices with color c induces a connected subgraph of G . In the Convex Recoloring problem a colored graph G χ is given, and the goal is to find a convex coloring χ ′ of G that recolors a minimum number of vertices. In the weighted version each vertex has a weight, and the goal is to minimize the total weight of recolored vertices. The 2-Convex Recoloring problem ( 2 -CR) is the special case, where the given coloring χ assigns the same color to at most two vertices. 2 -CR is known to be NP-hard even if G is a path. We show that weighted 2 -CR cannot be approximated within any ratio, unless P = NP . On the other hand, we provide an alternative definition of (unweighted) 2 -CR in terms of maximum independent set of paths, which leads to a natural greedy algorithm. We prove that its approximation ratio is 3 2 and show that this analysis is tight. This is the first constant factor approximation algorithm for a variant of CR in general graphs. For the special case, where G is a path, the algorithm obtains a ratio of 5 4 , an improvement over the previous best known approximation. We also consider the problem of determining whether a given graph has a convex recoloring of size k . We use the above mentioned characterization of 2 -CR to show that a problem kernel of size 4 k can be obtained in linear time and to design an O ( | E | ) + 2 O ( k log k ) time algorithm for parameterized 2 -CR.

The packing chromatic number $$\chi _{\rho }(G)$$ of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets $$V_i$$ , $$i\in \{1,\ldots ,k\}$$ , where each $$V_i$$ is an i-packing. In this paper, we consider the packing chromatic number of several families of Sierpinski-type graphs. While it is known that this number is bounded from above by 8 in the family of Sierpinski graphs with base 3, we prove that it is unbounded in the families of Sierpinski graphs with bases greater than 3. On the other hand, we prove that the packing chromatic number in the family of Sierpinski triangle graphs $$ST^n_3$$ is bounded from above by 31. Furthermore, we establish or provide bounds for the packing chromatic numbers of generalized Sierpinski graphs $$S^n_G$$ with respect to all connected graphs G of order 4.

The maximum k-colorable subgraph problem (k-MCSP) is to color as many vertices as possible with at most k colors, such that no two adjacent vertices share the same color. We consider online algorithms for this NP -hard problem, and give bounds on their competitive ratio. We then consider a large family A of online sequential coloring algorithms and determine the smallest graphs for which no algorithm in A can produce an optimal solution to the k-MCSP. We then compare the performance of several online sequential coloring algorithms, using DIMACS benchmark instances. We finally consider the case where vertices colored at an early stage can receive a new color later on, as long as they remain colored.

In the paper, we show that the incidence chromatic number χi of a complete k-partite graph is at most Δ + 2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to Δ + 1 if and only if the smallest part has only one vertex (i.e., Δ = n − 1). Formally, for a complete k-partite graph G = Kr1,r2,...,rk with the size of the smallest part equal to r1 ≥ 1 we have χi(G)={Δ(G)+1if r1=1,Δ(G)+2if r1>1.$$\chi _i (G) = \left\{ {\matrix{{\Delta (G) + 1} & {{\rm{if}}\;r_1 = 1,} \cr {\Delta (G) + 2} & {{\rm{if}}\;r_1 > 1.} \cr } } \right.$$ In the paper we prove that the incidence 4-coloring problem for semicubic bipartite graphs is 𝒩𝒫-complete, thus we prove also the 𝒩𝒫-completeness of L(1, 1)-labeling problem for semicubic bipartite graphs. Moreover, we observe that the incidence 4-coloring problem is 𝒩𝒫-complete for cubic graphs, which was proved in the paper [12] (in terms of generalized dominating sets).

The on-line interval coloring and its variants are important combinatorial problems with many applications in network multiplexing, resource allocation and job scheduling. In this paper we present a new lower bound of 4.1626 for the asymptotic competitive ratio for the on-line coloring of intervals with bandwidth which improves the best known lower bound of 24 7 . For the on-line coloring of unit intervals with bandwidth we improve the lower bound of 1.831 to 2.

A lid-coloring (locally identifying coloring) of a graph is a proper coloring such that, for any edge uv, if u and v have distinct closed neighborhoods, then the set of colors used on vertices of the closed neighborhoods of u and v are distinct. The lid-chromatic number is the minimum number of colors used in a lid-coloring. In this paper we prove a relation between lid-coloring and a variation, called strong lid-coloring. With this, we obtain linear time algorithms to calculate the lid-chromatic number for some classes of graphs with few P 4 's, such as cographs, P 4 -sparse graphs and ( q , q − 4 ) -graphs. We also prove that the lid-chromatic number is O ( n 1 − e ) -inapproximable in polynomial time for every e > 0 , unless P = NP .

Two vertex colorings of a graph G are equivalent if they induce the same partition of the vertex set into color classes. The graphical Bell number B ( G ) is the number of non-equivalent vertex colorings of G . We determine a sharp lower bound on B ( G ) for graphs G of order n and maximum degree n − 3 , and we characterize the graphs for which the bound is attained.

Genetic algorithms (GAs) can be divided into two broad approaches, Michigan and Pittsburgh Approaches. In Pittsburg approach, one of the individuals (chromosomes) in the population becomes the solution of the problem being solved whereas in Michigan approach the whole population represents the solution. For example in the problem of vertex coloring, in Michigan approach, each chromosome encodes a color of a vertex and the set of all chromosomes in the population represents the solution which is a coloring for the graph whereas in the Pittsburgh approach each individual encodes a coloring for the whole graph. Combining a genetic algorithm (GA) with a local search produces a type of evolutionary algorithm (EA) known as a memetic algorithm (MA). MA uses the local search method to either accelerate the discovery of good solutions, for which evolution alone would take too long to discover, or to reach solutions that would otherwise be unreachable by evolution or a local search method alone. In this paper a Michigan memetic algorithm for solving vertex coloring problem is proposed. The initial population is a set of chromosomes each of which is associated to a vertex of the input graph. Each chromosome is a part of the solution and represents a color for its corresponding vertex. The proposed algorithm is a distributed algorithm in which each chromosome locally evolves by evolutionary operators and improves by a learning automata based local search. To evaluate the efficiency of the proposed algorithm several computer experimentations have been conducted. The results show the superiority of the proposed algorithm over existing algorithms in terms of running time and the required number of colors.

The minimum sum coloring problem ( M S C P ) is a vertex coloring problem in which a weight is associated with each color. Its aim is to find a coloring of the vertices of a graph G with the minimum sum of the weights of the used colors. The M S C P has important applications in the fields such as scheduling and VLSI design. The minimum number of colors among all optimal solutions of the M S C P for G is called the chromatic strength of G and is denoted by s ( G ) . A tight upper bound of s ( G ) allows to significantly reduce the search space when solving the M S C P . In this paper, we propose and empirically evaluate two new upper bounds of s ( G ) for general graphs, U B A and U B S , based on an abstraction of all possible colorings of G formulated as an ordered set of decreasing positive integer sequences. The experimental results on the standard benchmarks DIMACS and COLOR show that U B A is competitive, and that U B S is significantly tighter than those previously proposed in the literature for 70 graphs out of 74 and, in particular, reaches optimality for 8 graphs. Moreover, both U B A and U B S can be applied to the more general optimum cost chromatic partition ( O C C P ) problem.

In this paper, a novel GPS-assisted grouping scheme is proposed to reduce the operational cost of cognitive radio networks with femtocells. This scheme allows the cognitive base station (CBS) to determine the minimum number of channels to be rented from the primary user (PU) networks by utilizing greedy graph coloring and frequency re-use. The proposed scheme is optimized, in terms of the distances between the FBSs in the same group, and extended to the co-channel deployment case (i.e., when the macrocell secondary users (MSUs) and the FBSs are operating on the same spectrum band). Moreover, the performance of the scheme is analyzed in terms of the average number of CBS channels, average outage probability, and complexity. Furthermore, two benchmark schemes are devised and compared to the distance-based greedy coloring scheme; namely, the optimal distance-based and the profit maximization schemes. Simulation results show that the performance of the distance-based greedy coloring scheme, in terms of reducing the number of channels to be purchased from the PU networks, approaches that of the optimal scheme in high interference environments.

A proper edge coloring f of a graph G with colors 1 , 2 , 3 , … , t is called an interval coloring if the colors on the edges incident to every vertex of G form an interval of integers. The coloring f is cyclic interval if for every vertex v of G , the colors on the edges incident to v either form an interval or the set { 1 , … , t } ∖ { f ( e ) : e is incident to v } is an interval. A bipartite graph G is ( a , b ) -biregular if every vertex in one part has degree a and every vertex in the other part has degree b ; it has been conjectured that all such graphs have interval colorings. We prove that every ( 3 , 5 ) -biregular graph has a cyclic interval coloring and we give several sufficient conditions for a ( 3 , 5 ) -biregular graph to admit an interval coloring.

In this survey the following types of colorings of plane graphs are discussed, both in their vertex and edge versions: facially proper coloring, rainbow coloring, antirainbow coloring, loose coloring, polychromatic coloring, l -facial coloring, nonrepetitive coloring, odd coloring, unique-maximum coloring, WORM coloring, ranking coloring and packing coloring. In the last section of this paper we show that using the language of words these different types of colorings can be formulated in a more general unified setting.