Abstract:
State of the art maximum clique algorithms use a greedy graph colouring as a bound. We show that greedy graph colouring can be misleading, which has implications for parallel branch and bound.

Abstract:
In graph theory, Graph Colouring Problem (GCP) is an assignment of colours to vertices of any given graph such that the colours on adjacent vertices are different. The GCP is known to be an optimization and NP-hard problem. Imperialist Competitive Algorithm (ICA) is a meta-heuristic optimization and stochastic search strategy which is inspired from socio-political phenomenon of imperialistic competition. The ICA contains two main operators: the assimilation and the imperialistic competition. The ICA has excellent capabilities such as high convergence rate and better global optimum achievement. In this research, a discrete version of ICA is proposed to deal with the solution of GCP. We call this algorithm as the DICA. The performance of the proposed method is compared with Genetic Algorithm (GA) on seven well-known graph colouring benchmarks. Experimental results demonstrate the superiority of the DICA for the benchmarks. This means DICA can produce optimal and valid solutions for different GCP instances.

Abstract:
A vertex colouring of a graph is \emph{nonrepetitive on paths} if there is no path $v_1,v_2,...,v_{2t}$ such that v_i and v_{t+i} receive the same colour for all i=1,2,...,t. We determine the maximum density of a graph that admits a k-colouring that is nonrepetitive on paths. We prove that every graph has a subdivision that admits a 4-colouring that is nonrepetitive on paths. The best previous bound was 5. We also study colourings that are nonrepetitive on walks, and provide a conjecture that would imply that every graph with maximum degree $\Delta$ has a $f(\Delta)$-colouring that is nonrepetitive on walks. We prove that every graph with treewidth k and maximum degree $\Delta$ has a $O(k\Delta)$-colouring that is nonrepetitive on paths, and a $O(k\Delta^3)$-colouring that is nonrepetitive on walks.

In the multiple
protocol label-switched (MPLS) networks, the commodities are transmitted by the
label-switched paths (LSPs). For the sake of reducing the total cost and
strengthening the central management, the MPLS networks restrict the number of
paths that a commodity can use, for maintaining the quality of service (QoS) of
the users, the demand of each commodity must be satisfied. Under the above
conditions, some links in the network may be too much loaded, affecting the
performance of the whole network drastically. For this problem, in[1], we proposed two mathematical
models to describe it and a heuristic algorithm which quickly finds
transmitting paths for each commodity are also presented. In this paper, we
propose a new heuristic algorithm which finds a feasible path set for each
commodity, and then select some paths from the path set through a mixed integer
linear programming to transmit the demand of each commodity. This strategy
reduces the scale of the original problem to a large extent. We test 50
instances and the results show the effectiveness of the new heuristic
algorithm.

Abstract:
A $k$-frugal colouring of a graph $G$ is a proper colouring of the vertices of $G$ such that no colour appears more than $k$ times in the neighbourhood of a vertex. This type of colouring was introduced by Hind, Molloy and Reed in 1997. In this paper, we study the frugal chromatic number of planar graphs, planar graphs with large girth, and outerplanar graphs, and relate this parameter with several well-studied colourings, such as colouring of the square, cyclic colouring, and $L(p,q)$-labelling. We also study frugal edge-colourings of multigraphs.

Abstract:
In this paper, we give the maximal number of (k+r)-colouring of a graph with n vertices and chromatic number k. Also, we obtain the maximal values for chromatic polynomial of a graph.

Abstract:
We show that, given an infinite cardinal $\mu$, a graph has colouring number at most $\mu$ if and only if it contains neither of two types of subgraph. We also show that every graph with infinite colouring number has a well-ordering of its vertices that simultaneously witnesses its colouring number and its cardinality.

Abstract:
This chapter presents an introduction to graph colouring algorithms. The focus is on vertex-colouring algorithms that work for general classes of graphs with worst-case performance guarantees in a sequential model of computation. The presentation aims to demonstrate the breadth of available techniques and is organized by algorithmic paradigm.

Abstract:
We deal with a graph colouring problem that arises in quantum information theory. Alice and Bob are each given a $\pm1$-vector of length $k$, and are to respond with $k$ bits. Their responses must be equal if they are given equal inputs, and distinct if they are given orthogonal inputs; however, they are not allowed to communicate any information about their inputs. They can always succeed using quantum entanglement, but their ability to succeed using only classical physics is equivalent to a graph colouring problem. We resolve the graph colouring problem, thus determining that they can succeed without entanglement exactly when $k\leq3$.

Abstract:
A graph G = (V, E) is said to be topogenic if it admits a topogenic set indexer, which is a set indexer f: V 2X such that f(V) is a topology on X. A list colouring of a graph G = (V,E) with a colour list C = for V = {v1, v2, ….vn} is a proper colouring of V by element of so that the adjacent vertices u,v are coloured differently and the colour for is in C(V). L- edge colouring of a graph G is an assignment L:E(G) 2X- such that no two adjacent edges receive the same label where X is a ground set. A graph G is to be L- edge colourable if there exists an L- edge colouring of G. A comparative study of topogenic graphs and L- edge colourable graphs has been made in this paper.