Narrow Results

An equitable dominator coloring of a graph $G$ is a proper vertex coloring of $G$ such that every vertex dominates at least one color class and the cardinalities of any two color classes differ by at most 1. The minimum number of colors used in the equitable dominator coloring of $G$ is called its equitable dominator chromatic number, denoted by ${\chi }_{ed}(G)$. This paper discusses the equitable dominator coloring of various helm-related graphs by obtaining their equitable dominator chromatic numbers.

Inspired by a real-life application, we investigate the computationally hard problem of extending a precoloring of an interval graph to a proper coloring under some bound on the number of available colors. We are interested in quickly determining whether or not such an extension exists on instances occurring in practice in connection with campsite bookings on a campground. A naive exhaustive search does not terminate in reasonable time. We have formulated a new approach which moves the computation time within the usable range on all the data samples available to us.

We consider an online model where an adversary constructs a set of $2^s$ instances $S$ instead of one single instance. The algorithm knows $S$ and the adversary will choose one instance from $S$ at random to present to the algorithm. We further focus on adversaries that construct sets of $k$-chromatic instances. In this setting, we provide upper and lower bounds on the competitive ratio for the online graph coloring problem as a function of the parameters in this model. Both bounds are linear in $s$ and matching upper and lower bound are given for a specific set of algorithms that we call “minimalistic online algorithms”.

In this paper we consider the following game: players must alternately color the lowest numbered uncolored vertex of a given graph G= ({1, 2,…, n}, E) with a color, taken from a given set C, such that two adjacent vertices are never colored with the same color. In one variant, the first player which is unable to move, loses the game. In another variant, player 1 wins the game if and only if the game ends with all vertices colored. We show that for both variants, the problem of determining whether there is a winning strategy for player 1 is PSPACE-complete for any C with |C|≥3, but the problems are solvable in , and time, respectively, if |C|=2. We also give polynomial time algorithms for the problems with certain restrictions on the graphs and orderings of the vertices. We give some partial results for the versions where no order for coloring the vertices is specified.

This paper presents an O((r–n/m)^mrnm) algorithm for determining whether a set of n species has a perfect phylogeny, where m is the number of characters used to describe a species and r is the maximum number of states that a character can be in. The perfect phylogeny algorithm leads to an O((2e/k)^ke²k) algorithm for triangulating a k-colored graph having e edges.

Evidence is given to suggest that minimally vertex colouring an interval graph may not be in NC¹. This is done by showing that 3-colouring a linked list is NC¹-reducible to minimally colouring an interval graph. However, it is shown that an interval graph with a known interval representation and an O(1) chromatic number can be minimally coloured in NC¹.

For the CRCW PRAM model, an o(log n) time, polynomial processors algorithm is obtained for minimally colouring an interval graph with o(log n) chromatic number and a known interval representation. In particular, when the chromatic number is O((log n)^1-ε), 0<ε<1, the algorithm runs in O(log n/log log n) time. Also, an O(log n) time, O(n) cost, EREW PRAM algorithm is found for interval graphs of arbitrary chromatic numbers. The following lower bound result is also obtained: even when the left and right endpoints of the interval are separately sorted, minimally colouring an interval graph needs Ω(log n/log log n) time, on a CRCW PRAM, with a polynomial number of processors.

Tabu search (TS) has always been a very popular algorithm for graph coloring, both as a stand-alone optimizer as well as a subroutine inside population-based hybrid methods. We present two TS extensions that could allow previous TS algorithms to improve their behavior at almost no additional computational cost. First, we integrate two new evaluation functions which employ supplementary (structural or dynamic) information in addition to the conventional objective function (the number of edges with both ends of the same color). These new evaluation functions allow the search process to differentiate configurations not distinguished by the conventional evaluation function. The second extension concerns a reactive mechanism for improving the tabu list management. Theoretical arguments show that this reactive component completely eliminates the risk of getting blocked looping on plateaus. Numerical experiments show that the two proposed TS extensions can be very useful inside a stand-alone TS optimizer, as well as inside TS subroutines of state-of-the-art hybrid methods.

This paper presents an extraction and expansion approach for the graph coloring problem. The extraction phase transforms a large graph into a sequence of progressively smaller graphs by removing large independent sets from the graph. The expansion phase starts by generating an approximate coloring for the smallest graph in the sequence. Then it expands the smallest graph by progressively adding back the extracted independent sets and determine a coloring for each intermediate graph. To color each graph, a simple perturbation based tabu search algorithm is used. The proposed approach is evaluated on the DIMACS challenge benchmarks showing competitive results in comparison with the state-of-the-art methods.

Multiple project wafers (MPWs) containing different chip designs from many customers serves as an important vehicle for gaining access to advanced semiconductor process technology for prototyping innovative designs or low-volume production. In this paper, a comprehensive study on the methods for determining dicing plans for MPW was carried out. Dicing plans can be used to determine the number of MPWs needed to be fabricated before chip fabrication and employed to saw the wafers after fabrication. Several methods based on integer linear programming formulation and a heuristic based on simulated annealing was proposed. Through conducting experiments with industrial test cases, these proposed methods can achieve up to 50% wafer reduction in some cases and on average 18% and 38% reduction for low- and high-volume production, respectively. This study makes a contribution to MPW dicing and is also instrumental in developing better reticle floorplanning methods.

The old problem of determining the chromatic number of the plane is revisited.

For a digraph ℍ, the Constraint Satisfaction Problem with template ℍ, or CSP(ℍ), is the problem of deciding whether a given input digraph 𝔾 admits a homomorphism to ℍ. The CSP dichotomy conjecture of Feder and Vardi states that for any digraph ℍ, CSP(ℍ) is either in P or NP-complete. Barto, Kozik, Maróti and Niven (Proc. Amer. Math. Soc.137 (2009) 2921–2934) confirmed the conjecture for a class of oriented trees called special triads. We generalize this result, establishing the dichotomy for a class of oriented trees which we call special polyads. We prove that every tractable special polyad has bounded width and provide the description of special polyads of width 1. We also construct a tractable special polyad which neither has width 1 nor admits any near-unanimity polymorphism.

Hassler Whitney's theorem of 1931 reduces the task of finding proper, vertex 4-colorings of triangulations of the 2-sphere to finding such colorings for the class ℌ of triangulations of the 2-sphere that have a Hamiltonian circuit. This has been used by Whitney and others from 1936 to the present to find equivalent reformulations of the 4 Color Theorem (4CT). Recently there has been activity to try to use some of these reformulations to find a shorter proof of the 4CT. Every triangulation in ℌ has a dual graph that is a union of two binary trees with the same number of leaves. Elements of a group known as Thompson's group F are equivalence classes of pairs of binary trees with the same number of leaves. This paper explores this resemblance and finds that some recent reformulations of the 4CT are essentially attempting to color elements of ℌ using expressions of elements of F as words in a certain generating set for F. From this, we derive information about not just the colorability of certain elements of ℌ, but also about all possible ways to color these elements. Because of this we raise (and answer some) questions about enumeration. We also bring in an extension E of the group F and ask whether certain elements "parametrize" the set of all colorings of the elements of ℌ that use all four colors.

Standard tabu search methods are based on the complete exploration of current solution neighborhood. However, for some problems due to the neighborhood size or to the fitness evaluation complexity, the total exploration of the neighborhood is impractical. The main purpose of this paper is to propose a local search method with no enumeration procedure. In other words, a single solution is examined at each iteration and retained for the future iterations. The idea is to randomly select one solution among a sub-set of the neighborhood of the current one. An adaptive exploration of neighborhood, using extension and restriction mechanisms represented by loop detection and tabu list structure, determines this sub-set. This approach is applied to the K-coloring problem and evaluated on standard benchmarks like DIMACS. The objective is to show how a generic method, without full neighborhood exploration, degradation control and problem-oriented operators, provides a very competitive results comparing to the best dedicated algorithms for graph coloring problems published in the literature.

Graph Coloring Boid Swarm (GCBS) is the successful application of Reynolds' Boid Swarm to solve the graph coloring problem, following appropriate mapping of the problem into boids' behaviors and interpretation of the global swarm states as problem solutions. A population P of boids moves in a closed torus-shaped space S. Each individual boid perceives a disk of radius R of its surrounding space, being able to exchange information with other boids lying inside this area of perception. Two mutually perceiving boids exchanging information are connected. In this paper we show that the ratio of the radius of perception to the space size can be critical for the convergence of the Boid Swarm to the optimal configurations. First, we derive the Percolation threshold for Elementary Boid Swarms (EBS), whose dynamics are the aggregation of the boids into spatial clusters. When the radius of perception is above this percolation threshold for Elementary Boid Swarms (EBS), whose dynamics are the aggregation of the boids into spatial clusters. When the radius of perception is above this percolation threshold there is complete connectivity and convergence to a single cluster. Second, we show empirically the existence of such a Percolation effect on the Graph Coloring Boid Swarm (GCBS). We find that complete connectivity has an adverse effect on the performance of the GCBS. Finally we show a comparison of GCBS with some other algorithms over a family of generated graphs.

If $\mathrm{\Gamma }$ is a closed Noetherian graph on a $\sigma$-compact Polish space with no infinite cliques, it is consistent with the choiceless set theory ZF$+$DC that $\mathrm{\Gamma }$ is countably chromatic and there is no Vitali set.

Recently, Kearns et al. [Kearns, M., Suri, S. and Montfort, N., An experimental study of the coloring problem on human subject networks, Science313 (2006) 824–827] studied the topology dependence of graph coloring dynamics. In their empirical study, the authors analyze, how a network of human subjects acting as autonomous agents performs in solving a conflict-avoidance task (the graph coloring problem) for different network architectures. A surprising result was that the run-time of the empirical dynamics decreases with the number of shortcuts in a Watts–Strogatz small-world graph. In a simulation of the dynamics based on randomly selecting color conflicts for update, they observe a strong increase of the run-time with the number of shortcuts. Here, we propose classes of strategies, which are capable of explaining the decrease in run-time with an increasing number of shortcuts. We show that the agent's strategy, the graph topology, and the complexity of the problem (essentially given by the graph's chromatic number) interact nontrivially yielding unexpected insights into the problem-solving capacity of organizational structures.

Motivated from the theory of quantum error correcting codes, we investigate a combinatorial problem that involves a symmetric n-vertices colorable graph and a group of operations (coloring rules) on the graph: find the minimum sequence of operations that maps between two given graph colorings. We provide an explicit algorithm for computing the solution of our problem, which in turn is directly related to computing the distance (performance) of an underlying quantum error correcting code. Computing the distance of a quantum code is a highly non-trivial problem and our method may be of use in the construction of better codes.

Coloring the vertices of a graph $G$ according to certain conditions is a random experiment and a discrete random variable $X$ is defined as the number of vertices having a particular color in the given type of coloring of $G$ and a probability mass function for this random variable can be defined accordingly. An equitable coloring of a graph $G$ is a proper coloring ${𝒞}$ of $G$ which an assignment of colors to the vertices of $G$ such that the numbers of vertices in any two color classes differ by at most one. In this paper, we extend the concepts of arithmetic mean and variance, the two major statistical parameters, to the theory of equitable graph coloring and hence determine the values of these parameters for a number of standard graphs.

Let $G$ be a graph. A vertex coloring $\psi$ of $G$ is called $N_2$-vertex coloring if $|\psi (v)|\le 2$ for every vertex $v$ of $G$, where $\psi (v)$ is the set of colors of vertices adjacent to $v$. Let $t_2(G)$ be the maximum number of colors used in an $N_2$-vertex coloring of $G$. We provide some lower and upper bounds for $t_2(G)$ in terms of girth, diameter or size of $G$. Also, for every tree $T$, we obtain $t_2(T)$.

Coloring the vertices of a graph $G$ according to certain conditions can be considered as a random experiment and a discrete random variable $X$ can be defined as the number of vertices having a particular color in the proper coloring of $G$. The concepts of mean and variance, two important statistical measures, have also been introduced to the theory of graph coloring and determined the values of these parameters for a number of standard graphs. In this paper, we discuss the coloring parameters of the Mycielskian of certain standard graphs.