Search

International audience; We show that the choice number of the square of a subcubic graph with maximum average degree less than 18/7 is at most 6. As a corollary, we get that the choice number of the square of a subcubic planar graph with girth at least 9 is at most 6. We then show that the choice number of the square of a subcubic planar graph with girth at least 13 is at most 5.

Hoang-Reed conjecture asserts that every digraph D has a collection C of circuits C"1,...,C"@d"^"+, where @d^+ is the minimum outdegree of D, such that the circuits of C have a forest-like structure. Formally, |V(C"i)@?(V(C"1)@?...@?V(C"i"-"1))|=

A (p,1)-total labelling of a graph G is an assignment of integers to V(G)@?E(G) such that: (i) any two adjacent vertices of G receive distinct integers, (ii) any two adjacent edges of G receive distinct integers, and (iii) a vertex and its incident edge receive integers that differ by at least p in absolute value. The span of a (p,1)-total labelling is the maximum difference between two labels. The minimum span of a (p,1)-total labelling of G is called the (p,1)-total number and denoted by @l"p^T(G). We provide lower and upper bounds for the (p,1)-total number. In particular, generalizing the Total Colouring Conjecture, we conjecture that @l"p^T=

A basic problem in the design of mobile telephone networks is to assign sets of radio frequency bands (colours) to transmitters (vertices) to avoid interference. Often the transmitters are laid out like vertices of a triangular lattice in the plane. We investigate the corresponding colouring problem of assigning sets of colours of size p(v) to each vertex of the triangular lattice so that the sets of colours assigned to adjacent vertices are disjoint. A n-[p]colouring of a graph G is a mapping c from V(G) into the set of the subsets of {1,2,…,n} such that |c(v)|=p(v) and for any adjacent vertices u and v, c(u)∩c(v)=∅. We give here an alternative proof of the fact that every triangular-free induced subgraph of the triangular lattice is 5-[2]colourable. This proof yields a constant time distributed algorithm that finds a 5-[2]colouring of such a graph. We then give a distributed algorithm that finds a [p]colouring of a triangle-free induced subgraph of the triangular lattice with at most 5ωp(G)/4+3 colours.

A basic problem in the design of mobile telephone networks is to assign sets of radio frequency bands (colours) to transmitters (vertices) to avoid interference. Often the transmitters are laid out like vertices of a triangular lattice in the plane. We investigate the corresponding colouring problem of assigning sets of colours of given size k to vertices of the triangular lattice so that the sets of colours assigned to adjacent vertices are disjoint. We prove here that every triangle-free induced subgraph of the triangular lattice is ⌈7k/3⌉-[k]colourable. That means that it is possible to assign to each transmitter of such a network, k bands of a set of ⌈7k/3⌉, so that there is no interference.

We give a short proof of the following theorem due to Borodin (1990) [2]. Every planar graph G with maximum degree at least 9 is (@D(G)+1)-edge-choosable.

The Grundy number of a graph G, denoted by @C(G), is the largest k such that G has a greedyk-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this paper, we study the Grundy number of the lexicographic and cartesian products of two graphs in terms of the Grundy numbers of these graphs. Regarding the lexicographic product, we show that @C(G)[email protected](H)@[email protected](G[H])@?2^@C^(^G^)^-^1(@C(H)-1)[email protected](G). In addition, we show that if G is a tree or @C(G)[email protected](G)+1, then @C(G[H])[email protected](G)[email protected](H). We then deduce that for every fixed c>=1, given a graph G, it is CoNP-Complete to decide if @C(G)@[email protected](G) and it is CoNP-Complete to decide if @C(G)@[email protected](G). Regarding the cartesian product, we show that there is no upper bound of @C([email protected]?H) as a function of @C(G) and @C(H). Nevertheless, we prove that @C([email protected]?H)@[email protected](G)@?2^@C^(^H^)^-^[email protected](H).