Local Nature of Brooks’ Colouring for Degree 3 Graphs

It is shown that for any two vertices u and v that are more than a constant distance apart in a 3-degree Brooks graph G, there exist two distinct 3-colourings of G of which one has u and v coloured the same, and the other has u and v coloured differently. Thus, in Brooks colouring, fixing the colour of one vertex does not fix the colour of vertices arbitrarily far away. In contrast, while 2-colouring a linked list, fixing the colour of one vertex fixes the colour of all others. This highly local nature of the problem can be seen as suggesting that, vis-a-vis the problem of 2-colouring a linked list, Brooks colouring may have a faster parallel algorithm. Acknowledgments.We wish to thank the referees for careful reading and their comments.     

A note on on-line ranking number of graphs

A k-ranking of a graph G = (V, E) is a mapping ϕ: V → {1, 2, ..., k} such that each path with end vertices of the same colour c contains an internal vertex with colour greater than c. The ranking number of a graph G is the smallest positive integer k admitting a k-ranking of G. In the on-line version of the problem, the vertices v ₁, v ², ..., v _n of G arrive one by one in an arbitrary order, and only the edges of the induced graph G[{v ₁, v ₂, ..., v _i }] are known when the colour for the vertex v _i has to be chosen. The on-line ranking number of a graph G is the smallest positive integer k such that there exists an algorithm that produces a k-ranking of G for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete n-partite graphs. The question of additivity and heredity is discussed as well.     

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.     

Properly coloured copies and rainbow copies of large graphs with small maximum degree

Let G be a graph on n vertices with maximum degree Δ. We use the Lovász local lemma to show the following two results about colourings χ of the edges of the complete graph K_n. If for each vertex v of K_n the colouring χ assigns each colour to at most (n ‐ 2)/(22.4Δ²) edges emanating from v, then there is a copy of G in K_n which is properly edge‐coloured by χ. This improves on a result of Alon, Jiang, Miller, and Pritikin [Random Struct. Algorithms 23(4), 409–433, 2003]. On the other hand, if χ assigns each colour to at most n/(51Δ²) edges of K_n, then there is a copy of G in K_n such that each edge of G receives a different colour from χ. This proves a conjecture of Frieze and Krivelevich [Electron. J. Comb. 15(1), R59, 2008]. Our proofs rely on a framework developed by Lu and Székely [Electron. J. Comb. 14(1), R63, 2007] for applying the local lemma to random injections. In order to improve the constants in our results we use a version of the local lemma due to Bissacot, Fernández, Procacci, and Scoppola [preprint, arXiv:0910.1824]. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 425–436, 2012     

Fractionally colouring total graphs

Bchzad and Vizing have conjectured that given any simple graph of maximum degree , one can colour its edges and vertices with +2 colours so that no two adjacent vertices, or two incident edges, or an edge and either of its ends receive the same colour. We show that for any simple graphG, V(G)E(G) can be fractionally coloured with +2 colours.     

On four-colourings of the rational four-space

Summary LetQ ⁴ denote the graph, obtained from the rational points of the 4-space, by connecting two points iff their Euclidean distance is one. It has been known that its chromatic number is 4. We settle a problem of P. Johnson, showing that in every four-colouring of this graph, every colour class is every-where dense.     

Parity vertex colouring of plane graphs

A proper vertex colouring of a 2-connected plane graph G is a parity vertex colouring if for each face f and each colour c, either no vertex or an odd number of vertices incident with f is coloured with c. The minimum number of colours used in such a colouring of G is denoted by χ_p(G).In this paper, we prove that χ_p(G)≤118 for every 2-connected plane graph G.     

XOR-based Visual Cryptography Schemes

A recent publication introduced a Visual Crypto (VC) system, based on the polarisation of light. This VC system has goodresolution, contrast and colour properties.Mathematically, the VC system is described by the XOR operation (modulo two addition). In this paper we investigate Threshold Visual Secret Sharing schemes associated to XOR-based VC systems. Firstly, we show that n out of n schemes with optimal resolution and contrast exist, and that (2,n) schemes are equivalent to binary codes. It turns out that these schemes have much better resolution than their OR-based counterparts. Secondly, we provide two explicit constructions for general k out of n schemes. Finally, we derive bounds on the contrast and resolution of XOR-based schemes. It follows from these bounds that for k<n, the contrast is strictly smaller than one. Moreover, the bounds imply that XOR-based k out of n schemes for even k are fundamentally different from those for odd k.AMS Classification: 94A60     

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.     

The total-chromatic number of some families of snarks

The total-chromatic numberχ_T(G) is the least number of colours needed to colour the vertices and edges of a graph G such that no incident or adjacent elements (vertices or edges) receive the same colour. It is known that the problem of determining the total-chromatic number is NP-hard, and it remains NP-hard even for cubic bipartite graphs. Snarks are simple connected bridgeless cubic graphs that are not 3-edge-colourable. In this paper, we show that the total-chromatic number is 4 for three infinite families of snarks, namely, the Flower Snarks, the Goldberg Snarks, and the Twisted Goldberg Snarks. This result reinforces the conjecture that all snarks have total-chromatic number 4. Moreover, we give recursive procedures to construct a total-colouring that uses 4 colours in each case.     

An extension of Vizing's theorem

Let G = (V (G), E (G)) be a simple graph of maximum degree δ ≤ D such that the graph induced by vertices of degree D is either a null graph or is empty. We give an upper bound on the number of colours needed to colour a subset S of V (G) ∪ E (G) such that no adjacent or incident elements of S receive the same colour. In particular, if S = E (G), we have the chromatic index χ′(G) ≤ D whereas if S = V (G) ∪ E (G) and for some positive integer k, we have the total chromatic number _χT(G) ≤ D + k. © 1997 John Wiley & Sons, Inc.     

Colorimetric estimation of rapox by ferric chloride solution

A method has been developed for estimating even one part per million RAPOX in aqueous medium using Lumetron photoelectric colorimeter 402-E and 620-M filter. The colour of RAPOX ferric complex has been found to obey Beer’s law in the range 10^?5?2·2×10^?4 mole per litre of the aqueous solution. The method depends on the development of colour on mixing aqueous RAPOX with ferric chloride solution in water.     

Colouring prime distance graphs

Four colours are necessary and sufficient to colour all the integers so that any two with difference equal to a prime have different colours. We investigate the corresponding problem when the setD of prescribed differences is a proper subset of the primes. In particular, we prove that ifD contains {2, 3} and also contains a pair of twin primes (one of which may be 3), then four colours are necessary. Numerous results regarding periodic colourings are also obtained. However, the problem of characterizing those setsD which necessitate four colours remains open.     

On Geometric Graph Ramsey Numbers

For any two-colouring of the segments determined by 3n − 3 points in general position in the plane, either the first colour class contains a triangle, or there is a noncrossing cycle of length n in the second colour class, and this result is tight. We also give a series of more general estimates on off-diagonal geometric graph Ramsey numbers in the same spirit. Finally we investigate the existence of large noncrossing monochromatic matchings in multicoloured geometric graphs. Research partially supported by Hungarian Scientific Research Grants OTKA T043631 and NK67867.     

On a problem of G. Hahn about coloured hamiltonian paths in K2t

We prove a theorem showing that for every integer p (p?2) there is a good minimal coloring of the edges of K_2^p such that every hamiltonian path in K_2^p uses at least one colour twice. This gives a counter-example to a conjecture of Hahn [2].     

ON UNIQUELY -G k-COLOURABLE GRAPHS

Abstract

Given graphs F and G and a nonnegative integer k, a map Π: V(F) → + {lm …, k} is a -G k-colouring of F if the subgraphs induced by each colour class do not contain G as an induced subgraph; F is -G k-chromatic if F has a -G k-colouring but no -G (k—1)-colouring. Further, we say F is uniquely -G k-colourable if and only if F is -G k-chromatic and, up to a permutation of colours, it has only one -G k-colouring. Such notions are extensions of the well known corresponding definitions from chromatic theory. In a previous paper (J. Graph. Th. 11 (1987), 87–99), the authors conjectured that for all graphs G of order at least two and all nonnegative integers k there exist uniquely -G k-colourable graphs. We show here that the conjecture holds whenever G or its complement is 2-connected.     

Vertex-Colouring Edge-Weightings

A weighting w of the edges of a graph G induces a colouring of the vertices of G where the colour of vertex v, denoted c_v, is . We show that the edges of every graph that does not contain a component isomorphic to K₂ can be weighted from the set {1, . . . ,30} such that in the resulting vertex-colouring of G, for every edge (u,v) of G, c_u ≠c_v.     

Adaptable chromatic number of graph products

A colouring of the vertices of a graph (or hypergraph) G is adapted to a given colouring of the edges of G if no edge has the same colour as both (or all) its vertices. The adaptable chromatic number of G is the smallest integer k such that each edge-colouring of G by colours 1,2,…,k admits an adapted vertex-colouring of G by the same colours 1,2,…,k. (The adaptable chromatic number is just one more than a previously investigated notion of chromatic capacity.) The adaptable chromatic number of a graph G is smaller than or equal to the ordinary chromatic number of G. While the ordinary chromatic number of all (categorical) powers G^k of G remains the same as that of G, the adaptable chromatic number of G^k may increase with k. We conjecture that for all sufficiently large k the adaptable chromatic number of G^k equals the chromatic number of G. When G is complete, we prove this conjecture with k≥4, and offer additional evidence suggesting it may hold with k≥2. We also discuss other products and propose several open problems.     

An upper bound for the total chromatic number

The total chromatic number,(G), of a graphG, is defined to be the minimum number of colours needed to colour the vertices and edges of a graph in such a way that no adjacent vertices, no adjacent edges and no incident vertex and edge are given the same colour. This paper shows that , where(G) is the vertex chromatic number and(G) is the edge chromatic number of the graph.Partially supported by ORS grant ORS/84120     

Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree

A proper vertex colouring of a graph G is 2-frugal (resp. linear) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph G is 2-frugally (resp. linearly) L-colourable if for a given list assignment L:V(G)? 2^{\mathbb N}{L:V(G)\mapsto 2^{\mathbb N}} , there exists a 2-frugal (resp. linear) colouring c of G such that c(v) ? L(v){c(v) \in L(v)} for all v ? V(G){v\in V(G)} . If G is 2-frugally (resp. linearly) L-list colourable for any list assignment such that |L(v)| ≥ k for all v ? V(G){v\in V(G)}, then G is 2-frugally (resp. linearly) k-choosable. In this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum average degree.