Colouring graphs with bounded generalized colouring number

Given a graph G and a positive integer p, χ_p(G) is the minimum number of colours needed to colour the vertices of G so that for any i≤p, any subgraph H of G of tree-depth i gets at least i colours. This paper proves an upper bound for χ_p(G) in terms of the k-colouring number of G for k=2^p−2. Conversely, for each integer k, we also prove an upper bound for in terms of χ_k+2(G). As a consequence, for a class K of graphs, the following two statements are equivalent:

(a)

For every positive integer p, χ_p(G) is bounded by a constant for all G∈K.

(b)

For every positive integer k, is bounded by a constant for all G∈K.

It was proved by Nešet?il and Ossona de Mendez that (a) is equivalent to the following:

(c)

For every positive integer q, ∇_q(G) (the greatest reduced average density of G with rank q) is bounded by a constant for all G∈K.

Therefore (b) and (c) are also equivalent. We shall give a direct proof of this equivalence, by introducing ∇_q−(1/2)(G) and by showing that there is a function F_k such that . This gives an alternate proof of the equivalence of (a) and (c).     

On the chromatic number of circulant graphs

Given a set D of a cyclic group C, we study the chromatic number of the circulant graph G(C,D) whose vertex set is C, and there is an edge ij whenever i−j∈D∪−D. For a fixed set D={a,b,c:a<b<c} of positive integers, we compute the chromatic number of circulant graphs G(Z_N,D) for all N≥4bc. We also show that, if there is a total order of D such that the greatest common divisors of the initial segments form a decreasing sequence, then the chromatic number of G(Z,D) is at most 4. In particular, the chromatic number of a circulant graph on Z_N with respect to a minimum generating set D is at most 4. The results are based on the study of the so-called regular chromatic number, an easier parameter to compute. The paper also surveys known results on the chromatic number of circulant graphs.     

Boxicity of Halin graphs

A k-dimensional box is the Cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if G is a Halin graph that is not isomorphic to K₄, then . In fact, we prove the stronger result that if G is a planar graph formed by connecting the leaves of any tree in a simple cycle, then unless G is isomorphic to K₄ (in which case its boxicity is 1).     

Finitely locally finite coverings of Banach spaces

A well-known result due to H. Corson states that, for any covering τ by closed bounded convex subsets of any Banach space X containing an infinite-dimensional reflexive subspace, there exists a compact subset C of X that meets infinitely many members of τ. We strengthen this result proving that, even under the weaker assumption that X contains an infinite-dimensional separable dual space, an (algebraically) finite-dimensional compact set C with that property can always be found.     

Adaptable choosability of planar graphs with sparse short cycles

Given a (possibly improper) edge colouring F of a graph G, a vertex colouring of G is adapted toF if no colour appears at the same time on an edge and on its two endpoints. A graph G is called (for some positive integer k) if for any list assignment L to the vertices of G, with |L(v)|≥k for all v, and any edge colouring F of G, G admits a colouring c adapted to F where c(v)∈L(v) for all v. This paper proves that a planar graph G is adaptably 3-choosable if any two triangles in G have distance at least 2 and no triangle is adjacent to a 4-cycle.     

Interleaving schemes on circulant graphs with two offsets

Interleaving is used for error-correcting on a bursty noisy channel. Given a graph G describing the topology of the channel, we label the vertices of G so that each label-set is sufficiently sparse. The interleaving scheme corrects for any error burst of size at most t; it is a labeling where the distance between any two vertices in the same label-set is at least t.We consider interleaving schemes on infinite circulant graphs with two offsets 1 and d. In such a graph the vertices are integers; edge ij exists if and only if |i−j|∈{1,d}. Our goal is to minimize the number of labels used.Our constructions are covers of the graph by the minimal number of translates of some label-set S. We focus on minimizing the index of S, which is the inverse of its density rounded up. We establish lower bounds and prove that our constructions are optimal or almost optimal, both for the index of S and for the number of labels.     

Super-vertex-antimagic total labelings of disconnected graphs

Let G=(V,E) be a finite, simple and non-empty (p,q)-graph of order p and size q. An (a,d)-vertex-antimagic total labeling is a bijection f from V(G)∪E(G) onto the set of consecutive integers 1,2,…,p+q, such that the vertex-weights form an arithmetic progression with the initial term a and the common difference d, where the vertex-weight of x is the sum of values f(xy) assigned to all edges xy incident to vertex x together with the value assigned to x itself, i.e. f(x). Such a labeling is called super if the smallest possible labels appear on the vertices.In this paper, we will study the properties of such labelings and examine their existence for disconnected graphs.     

Homogenization of monotone operators in divergence form with <Emphasis Type="Italic">x</Emphasis>-dependent multivalued graphs

In a previous paper [4], we proved the existence of solutions to −div a(x, grad u) = f , together with appropriate boundary conditions, whenever a(x, e) belongs, for every fixed x, to a certain class of maximal monotone graphs in e. Here, we derive the corresponding homogenization result, letting a(x, e) depend upon a parameter ε, and imposing adequate ε-uniform boundedness and coercivity properties. The resulting homogenized graphs belong to the same class of maximal monotone graphs. Our results do not assume any kind of periodicity.      

Small maximal matchings of random cubic graphs

We consider the expected size of a smallest maximal matching of cubic graphs. Firstly, we present a randomized greedy algorithm for finding a small maximal matching of cubic graphs. We analyze the average‐case performance of this heuristic on random n‐vertex cubic graphs using differential equations. In this way, we prove that the expected size of the maximal matching returned by the algorithm is asymptotically almost surely (a.a.s.) less than 0.34623n. We also give an existence proof which shows that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. less than 0.3214n. It is known that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. larger than 0.3158n. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 293–323, 2009     

Partial characterizations of circular‐arc graphs

A circular‐arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular‐arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to any of the following classes: P₄ ‐free graphs, paw‐free graphs, claw‐free chordal graphs and diamond‐free graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 289–306, 2009