The product representation of a locally dependent random graph

Directed graphs with random black and white colourings of edges such that the colours of edges from different vertices are mutually independent are called locally dependent random graphs. Two random graphs are equivalent if they cannot be distinguished from percolation processes on them if only the vertices are seen. A necessary and sufficient condition is given for when a locally dependent random graph is equivalent to a product random graph; that is one in which the edges can be grouped in such a way that within each group the colours of the edges are equivalent and between groups they are independent. As an application the random graph corresponding to a spatial general epidemic model is considered.     

Efficient bounds on a branch and bound algorithm for graph colouration

By a proper colouring of a simple graph, we mean an assignment of colours to its vertices with adjacent vertices receiving different colours. Applications of this graph‐theoretic modelling are numerous, especially in the areas of scheduling and timetabling. We shall refer to a proper colouration that uses a smallest possible number of colours as a minimum (proper) colouration. This number for the graph is simply its chromatic number, the determination of which is well known to be a ‘hard’ problem. In this paper, from the computational point of view of actually constructing a colouration, we examine a simple coalescence/expansion procedure that bases on the branch and bound technique improved by efficient bounding conditions. They include various tightened fathoming criteria as well as complete subgraph determination. For the computer implementation, we also look at the issues of branching rules and the decomposition of solution tree. With these efforts, empirical results show that minimum colourations can be constructed for moderate size graphs, with ‘good’ solutions computed for problems of up to about forty vertices.     

Acyclic improper colouring of graphs with maximum degree 4

A k-colouring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclic k-colourings such that each colour class induces a graph with a given(hereditary) property. In particular, we consider acyclic k-colourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyclic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with Δ(G) 4 can be acyclically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.     

Achromatic Number of K 5 × K n for Small n

The achromatic number of a graph G is the maximum number of colours in a proper vertex colouring of G such that for any two distinct colours there is an edge of G incident with vertices of those two colours. We determine the achromatic number of the Cartesian product of K ₅ and K _n for all n ≤ 24.     

A Vizing-type theorem for matching forests

A well-known Theorem of Vizing states that one can colour the edges of a graph by Δ+ colours, such that edges of the same colour form a matching. Here, Δ denotes the maximum degree of a vertex, and the maximum multiplicity of an edge in the graph. An analogue of this Theorem for directed graphs was proved by Frank. It states that one can colour the arcs of a digraph by Δ+ colours, such that arcs of the same colour form a branching. For a digraph, Δ denotes the maximum indegree of a vertex, and the maximum multiplicity of an arc. We prove a common generalization of the above two theorems concerning the colouring of mixed graphs (these are graphs having both directed and undirected edges) in such a way that edges of the same colour form a matching forest.     

The Proportional Colouring Problem: Optimizing Buffers in Wireless Mesh Networks

In this paper, we consider a new edge colouring problem motivated by wireless mesh networks optimization: the proportional edge colouring problem. Given a graph G with positive weights associated to its edges, we want to find a proper edge colouring which assigns to each edge at least a proportion (given by its weight) of all the colours. If such colouring exists, we want to find one using the minimum number of colours. We proved that deciding if a weighted graph admits a proportional edge colouring is polynomial while determining its proportional edge chromatic number is NP-hard. We also give a lower and an upper bound that can be polynomially computed. We finally characterize some graphs and weighted graphs for which we can determine the proportional edge chromatic number.     

Edge partitions of the Rado graph

We will prove that for every colouring of the edges of the Rado graph, (that is the countable homogeneous graph), with finitely many coulours, it contains an isomorphic copy whose edges are coloured with at most two of the colours. It was known [4] that there need not be a copy whose edges are coloured with only one of the colours. For the proof we use the lexicographical order on the vertices of the Rado graph, defined by Erdös, Hajnal and Pósa.Using the result we are able to describe a Ramsey basis for the class of Rado graphs whose edges are coloured with at most a finite number,r, of colours. This answers an old question of M. Pouzet.Supported by the French PRC Math-Info.Supported by NSERC of Canada Grant # 691325.     

A Note on Large Rainbow Matchings in Edge-coloured Graphs

A rainbow subgraph in an edge-coloured graph is a subgraph such that its edges have distinct colours. The minimum colour degree of a graph is the smallest number of distinct colours on the edges incident with a vertex over all vertices. Kostochka, Pfender, and Yancey showed that every edge-coloured graph on n vertices with minimum colour degree at least k contains a rainbow matching of size at least k, provided ${n\geq \frac{17}{4}k^2}$ . In this paper, we show that n ≥ 4k ? 4 is sufficient for k ≥ 4.     

On the Neighbour-Distinguishing Index of a Graph

A proper edge colouring of a graph G is neighbour-distinguishing provided that it distinguishes adjacent vertices by sets of colours of their incident edges. It is proved that for any planar bipartite graph G with Δ(G)≥12 there is a neighbour-distinguishing edge colouring of G using at most Δ(G)+1 colours. Colourings distinguishing pairs of vertices that satisfy other requirements are also considered.     

On the fractional chromatic index of a graph and its complement

Jensen and Toft conjectured that for a graph with an even number of vertices, either the minimum number of colours in a proper edge colouring is equal to the maximum vertex degree, or this is true in its complement. We prove a fractional version of this conjecture.     

An Anti-Ramsey Theorem

Let be the Turán number which gives the maximum size of a graph of order containing no subgraph isomorphic to . In 1973, Erdős, Simonovits and Sós [5] proved the existence of an integer such that for every integer , the minimum number of colours , such that every -colouring of the edges of which uses all the colours produces at least one all whose edges have different colours, is given by . However, no estimation of was given in [5]. In this paper we prove that for . This formula covers all the relevant values of n and p. Received January 27, 1997/Revised March 14, 2000     

Generalised acyclic edge colourings of graphs with large girth

The r-acyclic edge chromatic number of a graph G is the minimum number of colours required to colour the edges of G in such a way that adjacent edges receive different colours and every cycle C receives at least min{|C|,r} colours. We prove that for any integer r?4, the r-acyclic edge chromatic number of any graph G with maximum degree Δ and with girth at least 3(r-1)Δ is at most 6(r-1)Δ.     

Edge-switching homomorphisms of edge-coloured graphs

An edge-coloured graph G is a vertex set V(G) together with m edge sets distinguished by m colours. Let π be a permutation on {1,2,…,m}. We define a switching operation consisting of π acting on the edge colours similar to Seidel switching, to switching classes as studied by Babai and Cameron, and to the pushing operation studied by Klostermeyer and MacGillivray. An edge-coloured graph G is π-permutably homomorphic (respectively π-permutably isomorphic) to an edge-coloured graph H if some sequence of switches on G produces an edge-coloured graph homomorphic (respectively isomorphic) to H. We study the π-homomorphism and π-isomorphism operations, relating them to homomorphisms and isomorphisms of a constructed edge-coloured graph that we introduce called a colour switching graph. Finally, we identify those edge-coloured graphs H with the property that G is homomorphic to H if and only if any switch of G is homomorphic to H. It turns out that such an H is precisely a colour switching graph. As a corollary to our work, we settle an open problem of Klostermeyer and MacGillivray.     

Proper‐walk connection number of graphs

This paper studies the problem of proper‐walk connection number: given an undirected connected graph, our aim is to colour its edges with as few colours as possible so that there exists a properly coloured walk between every pair of vertices of the graph, that is, a walk that does not use consecutively two edges of the same colour. The problem was already solved on several classes of graphs but still open in the general case. We establish that the problem can always be solved in polynomial time in the size of the graph and we provide a characterization of the graphs that can be properly connected with $k$ colours for every possible value of $k$.     

On the P4-structure of perfect graphs. II. Odd decompositions

We prove that a graph is perfect if its vertices can be coloured by two colours in such a way that each induced chordless path with four vertices has an odd number of vertices of each colour. Using this result, we prove a decomposition theorem for perfect graphs; this theorem is defined in terms of the chordless path with four vertices.     

Analysis of a game of graph solitaire

Let G be a simple undirected graph. To each vertex assign one of two colours say red or blue. A solitaire game is played on G as follows. A move consists of selecting a blue vertex, inverting the colours of its neighbours and then deleting the chosen vertex and all edges incident upon it. The goal is to delete all the vertices. The question of finding a winning strategy in the case when G is a simple cycle was proposed in the problems section of the American Mathematical Monthly. In this article some general results on winning colour configurations are derived and the game is analysed for certain other graph classes.     

Representing Groups by Colourings of Graphs

The topic of this paper is representing groups by edge-coloured graphs. Every edge-coloured graph determines a group of graph automorphisms which preserve the colours of the edges. An edge colouring of a graph G is called a perfect one iff every colour class is a perfect matching in G. We prove that every group H and all of its subgroups can be represented (up to isomorphism) by a group of colour preserving automorphisms related to some perfect colouring of the same graph.     

Entire colouring of plane graphs

It was conjectured by Kronk and Mitchem in 1973 that simple plane graphs of maximum degree Δ are entirely (Δ+4)-colourable, i.e., the vertices, edges, and faces of a simple plane graph may be simultaneously coloured with Δ+4 colours in such a way that adjacent or incident elements are coloured by distinct colours. Before this paper, the conjecture has been confirmed for Δ?3 and Δ?6 (the proof for the Δ=6 case has a correctable error). In this paper, we settle the whole conjecture in the positive. We prove that if G is a plane graph with maximum degree 4 (parallel edges allowed), then G is entirely 8-colourable. If G is a plane graph with maximum degree 5 (parallel edges allowed), then G is entirely 9-colourable.     

Rainbowness of cubic plane graphs

The rainbowness, rb(G), of a connected plane graph G is the minimum number k such that any colouring of vertices of the graph G using at least k colours involves a face all vertices of which receive distinct colours. For a connected cubic plane graph G we prove that

     

Acyclic Choosability of Graphs with Bounded Degree

An acyclic colouring of a graph G is a proper vertex colouring such that every cycle uses at least three colours. For a list assignment L = {L(v)| v∈V(G)}, if there exists an acyclic colouringρ such that ρ(v)∈L(v) for each v∈V(G), then ρ is called an acyclic L-list colouring of G. If there exists an acyclic L-list colouring of G for any L with |L(v)|≥k for each v∈V(G), then G is called acyclically k-choosable. In this paper, we prove that every graph with maximum degree Δ≤7 is acyclically 13-cho...