EPSRC Reference: 
EP/G043434/1 
Title: 
Algorithmic Aspects of Graph Coloring 
Principal Investigator: 
Paulusma, Professor D 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Engineering and Computing Sciences 
Organisation: 
Durham, University of 
Scheme: 
Standard Research 
Starts: 
01 October 2009 
Ends: 
31 October 2013 
Value (£): 
437,514

EPSRC Research Topic Classifications: 
Fundamentals of Computing 


EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
29 Jan 2009

ICT Prioritisation Panel (January 2009)

Announced


Summary on Grant Application Form 
We consider a variety of practical situations in which attributes (wavelengths, frequencies, time slots, machines) have to be allocated to conflicting objects (optical data streams, transmitters, traffic streams, jobs) in such a way that no pair of conflicting objects receives the same attribute. We model such situations as graph coloring problems. A graph is given by a set of vertices that represent the objects and a set of unordered pairs of vertices, called edges, representing the conflicts between pairs of objects. Graph coloring involves the labeling of the vertices of some given graph by integers called colors such that no two adjacent vertices receive the same color. In many applications the objective is to minimize the number of colors. Graph coloring has been a popular research topic since its introduction as a map coloring problem more than 150 years ago. Some reasons for this are its appealingly simple definition, its large variety of open problems, and its many application areas. Whenever conflicting situations between pairs of objects can be modeled by graphs, and one is looking for a partition of the set of objects in subsets of mutually nonconflicting objects, this can be viewed as a graph coloring problem. This holds for classical settings such as neighboring countries (map coloring) or interfering jobs on machines (job scheduling), as well as for more recent settings like colliding data streams in optical networks (wavelength assignment), colliding traffic streams (time slot allocation) or interfering transmitters and receivers for broadcasting, mobile phones and sensors (frequency assignment), to name just a few. Note that even the nowadays so immensely popular passtime of Sudokus comes down to coloring a (partially precolored) graph on 81 vertices (representing the 81 squares of the Sudoku) with 9 colors (the integers 1 to 9).In the classical setting the coloring is done offline in the sense that the whole graph is known and it does not change over time. Many variants on this simple offline graph coloring concept have been defined and studied, mainly due to additional restrictions on the coloring. We illustrate this by considering the general framework for coloring problems related to frequency assignment. In this application area graphs are used to model the topology and mutual interference between transmitters (receivers, base stations): the vertices of the graph represent the transmitters; two vertices are adjacent in the graph if the corresponding transmitters are so close (or so strong) that they are likely to interfere if they broadcast on the same or `similar' frequency channels. The problem in practice is to assign the frequency channels to the transmitters in such a way that interference is kept at an `acceptable level'. In many technological applications offline coloring is not a suitable concept because complete information on the graph one has to color is not known beforehand, e.g. if jobs come in onebyone and have to be scheduled on machines right away and rescheduling is not possible. In this case one has to consider another variant of coloring, namely online graph coloring. In this setting the graph is presented vertex by vertex, and a vertex must irrevocably be assigned a color as it comes in, i.e. the choice of color is only based on the knowledge of the subgraph that has been revealed so far. In general, minimizing the number of colors is an NPhard problem (it is even more problematic in the online setting) . This means that most likely there is no polynomial time ( fast ) algorithm for this problem (an algorithm can be seen as a set of instructions for solving a problem). However, coloring problems occuring in specific situations with extra restrictions might have a different time complexity. Therefore, we try to design and analyse algorithms that solve graph coloring problems both in the on and offline setting for several variants as described in our proposal.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
