Concept
Four color theorem
Related publications (32)
On the Performance of Percolation Graph Matching
Matthias Grossglauser, Lyudmila Yartseva
Graph matching is a generalization of the classic graph isomorphism problem. By using only their structures a graph-matching algorithm finds a map between the vertex sets of two similar graphs. This has applications in the de-anonymization of social and in ...
ACM2013On coloring problems with local constraints
We deal with some generalizations of the graph coloring problem on classes of perfect graphs. Namely we consider the μ-coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand) ...
Elsevier2012On the power of combinatorial and spectral invariants
We extend the traditional spectral invariants (spectrum and angles) by a stronger polynomial time computable graph invariant based on the angles between projections of standard basis vectors into the eigenspaces (in addition to the usual angles between sta ...
2010Split-critical and uniquely split-colorable graphs
Dominique de Werra, Bernard Ries, Tinaz Ekim
The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring p ...
2010The potential to improve the choice: list conflict-free coloring for geometric hypergraphs
Given a geometric hypergraph (or a range-space) , a coloring of its vertices is said to be conflict-free if for every hyperedge there is at least one vertex in whose color is distinct from the colors of all other vertices i ...
2010Optimistic chordal coloring: a coalescing heuristic for SSA form programs
Paolo Ienne, Philip Brisk, Ajay Kumar Verma
The interference graph for a procedure in Static Single Assignment (SSA) Form is chordal. Since the k-colorability problem can be solved in polynomial-time for chordal graphs, this result has generated interest in SSA-based heuristics for spilling and coal ...
Springer US2009A tutorial on the use of graph coloring for some problems in robotics
Dominique de Werra, Tinaz Ekim
We study the problem where a robot has to pick up items of different sizes which are stored along a corridor. A natural requirement is that the items have to be collected in decreasing order of their sizes. We deal with various systems according to the loc ...
2009Graph colouring approaches for a satellite range scheduling problem
Nicolas Zufferey, Patrick Amstutz, Philippe Giaccari
A goal of this paper is to efficiently adapt the best ingredients of the graph colouring techniques to an NP-hard satellite range scheduling problem, called MuRRSP. We propose two new heuristics for the MuRRSP, where as many jobs as possible have to be sch ...
2008On the essential dimension of cyclic p-groups
Let p be a prime number, let K be a field of characteristic not p, containing the p-th roots of unity, and let r >= 1 be an integer. We compute the essential dimension of Z/p(r) Z over K (Theorem 4.1). In particular, i) We have edℚ(ℤ/8ℤ)=4, a result which ...
Springer-Verlag2008A graph coloring heuristic using partial solutions and a reactive tabu scheme
Most of the recent heuristics for the graph coloring problem start from an infeasible k-coloring (adjacent vertices may have the same color) and try to make the solution feasible through a sequence of color exchanges. In contrast, our approach (called FOO- ...
2008