By R. M. R. Lewis

This e-book treats graph colouring as an algorithmic challenge, with a powerful emphasis on useful purposes. the writer describes and analyses the various best-known algorithms for colouring arbitrary graphs, targeting no matter if those heuristics provides optimum ideas at times; how they practice on graphs the place the chromatic quantity is unknown; and whether or not they can produce larger suggestions than different algorithms for particular types of graphs, and why.

The introductory chapters clarify graph colouring, and boundaries and optimistic algorithms. the writer then indicates how complex, glossy concepts should be utilized to vintage real-world operational learn difficulties comparable to seating plans, activities scheduling, and collage timetabling. He contains many examples, feedback for extra examining, and ancient notes, and the publication is supplemented through an internet site with a web suite of downloadable code.

The booklet could be of price to researchers, graduate scholars, and practitioners within the components of operations study, theoretical laptop technological know-how, optimization, and computational intelligence. The reader must have straightforward wisdom of units, matrices, and enumerative combinatorics.

Similar graph theory books

Networks and Graphs: Techniques and Computational Methods

Dr Smith the following offers crucial mathematical and computational principles of community optimization for senior undergraduate and postgraduate scholars in arithmetic, desktop technological know-how and operational examine. He exhibits how algorithms can be utilized for locating optimum paths and flows, making a choice on timber in networks, and optimum matching.

Extra info for A Guide to Graph Colouring: Algorithms and Applications

Example text

G) > Δ (G). We therefore assume that all graphs with fewer vertices than G can be feasibly coloured using Δ (G) colours. Claim 1: G is connected. If G were not connected, then G’s components would be a smaller counterexample, or all of G’s components would be Δ (G)-colourable. Claim 2: G is 2-connected. If G were not 2-connected, then G would have at least one cut vertex v, and each block of G would be Δ (G)-colourable. The colourings of each block could then be combined to form a feasible Δ (G)-colouring.

The fact that graph colouring is NP-hard does not mean that no problem instances are solvable in polynomial time, however. As a trivial example, consider a graph comprising a vertex set V = {v1 , . . , vn } and edge set E = 0/ (such a graph is commonly known as an empty graph on n vertices). Obviously, since no pairs of vertices are adjacent in this graph, the n vertices can all be feasibly assigned the same single colour, giving a chromatic number of 1. In practice it would be easy to write an algorithm to check whether E = 0/ and, if this is the case, produce the corresponding optimal solution.

It is obvious, therefore, that a graph G features a chromatic number χ(G) = 2 if and only if it is bipartite. Fig. 11, shows three examples of bipartite graphs and their optimal colourings: an arbitrary bipartite graph; a tree (that is, a bipartite graph that contains no cycles); and a star graph. 3 Cycle, Wheel and Planar Graphs Cycle graphs, denoted by Cn , where n ≥ 3, comprise a set of vertices V = {v1 , . . , vn } and a set of edges E of the form {{v1 , v2 }, {v2 , v3 }, . . , {vn−1 , vn }, {vn , v1 }}.