Injective colorings of sparse graphs

Let denote the maximum average degree (over all subgraphs) of G and let χ_i(G) denote the injective chromatic number of G. We prove that if , then χ_i(G)≤Δ(G)+1; and if , then χ_i(G)=Δ(G). Suppose that G is a planar graph with girth g(G) and Δ(G)≥4. We prove that if g(G)≥9, then χ_i(G)≤Δ(G)+1; similarly, if g(G)≥13, then χ_i(G)=Δ(G).     

The homology of the cyclic coloring complex of simple graphs

Let G be a simple graph on n vertices, and let χG(λ) denote the chromatic polynomial of G. In this paper, we define the cyclic coloring complex, Δ(G), and determine the dimensions of its homology groups for simple graphs. In particular, we show that if G has r connected components, the dimension of (n−3)rd homology group of Δ(G) is equal to (n−(r+1)) plus , where is the rth derivative of χG(λ). We also define a complex ΔC(G), whose r-faces consist of all ordered set partitions [B₁,…,Br+2] where none of the Bi contain an edge of G and where 1∈B₁. We compute the dimensions of the homology groups of this complex, and as a result, obtain the dimensions of the multilinear parts of the cyclic homology groups of C[x₁,…,xn]/{xixj|ij is an edge of G}. We show that when G is a connected graph, the homology of ΔC(G) has nonzero homology only in dimension n−2, and the dimension of this homology group is . In this case, we provide a bijection between a set of homology representatives of ΔC(G) and the acyclic orientations of G with a unique source at v, a vertex of G.     

Moment conditions and support theorems for Radon transforms on affine Grassmann manifolds

Let G(p,n) and G(q,n) be the affine Grassmann manifolds of p- and q-planes in Rⁿ, respectively, and let be the Radon transform from smooth functions on G(p,n) to smooth functions on G(q,n) arising from the inclusion incidence relation. When p<q and dimG(p,n)=dimG(p,n), we present a range characterization theorem for via moment conditions. We then use this range result to prove a support theorem for . This complements a previous range characterization theorem for via differential equations when dimG(p,n)<dimG(p,n). We also present a support theorem in this latter case.     

Hamilton-connected indices of graphs

Let G be an undirected graph that is neither a path nor a cycle. Clark and Wormald [L.H. Clark, N.C. Wormald, Hamiltonian-like indices of graphs, ARS Combinatoria 15 (1983) 131-148] defined hc(G) to be the least integer m such that the iterated line graph L^m(G) is Hamilton-connected. Let be the diameter of G and k be the length of a longest path whose internal vertices, if any, have degree 2 in G. In this paper, we show that . We also show that κ³(G)≤hc(G)≤κ³(G)+2 where κ³(G) is the least integer m such that L^m(G) is 3-connected. Finally we prove that hc(G)≤|V(G)|−Δ(G)+1. These bounds are all sharp.     

The number of reachable pairs in a digraph

For a digraph G, let R(G) (respectively, R^(k)(G)) be the number of ordered pairs (u,v) of vertices of G such that u≠v and v is reachable from u (respectively, reachable from u by a path of length ?k). In this paper, we study the range S_n of R(G) and the range of R^(k)(G) as G varies over all possible digraphs on n vertices. We give a sufficient condition and a necessary condition for an integer to belong to S_n. These determine the set S_n for all n?208. We also determine for k?4 and show that whenever n?k+(k+1)^0.57+2, for arbitrary k.     

On the dual rigidity matrix

A novel characterization of bar-and-joint framework rigidity was introduced in [A.Y. Alfakih. Graph rigidity via Euclidean distance matrices. Linear Algebra Appl., 310 (2000) 149-165; A.Y. Alfakih. On rigidity and realizability of weighted graphs. Linear Algebra Appl., 325 (2001) 57-70]. This characterization uses the notion of normal cones of convex sets to define a matrix whose rank determines whether or not a given generic framework is rigid. Furthermore, this characterization was derived under the assumption that the framework of interest G(p) has an equivalent framework G(q) in R^n-1, where n is the number of vertices of G(p). In this paper we show that the matrix corresponding to a framework G(p) contains the same information as the well-known rigidity matrix R. Whereas the entries of R are a function of the positions of the vertices of G(p), the entries of are a function of the Gale matrix corresponding to G(p). Furthermore, while the number of rows of R is equal to the number of edges of G(p), the number of columns of is equal to the number of missing edges of G(p). We also show that the assumption of the existence of an equivalent framework G(q) in R^n-1 can be dropped and we give the precise relation between the left-nullspaces, and consequently the nullspaces, of R and .     

Rieffel deformation of homogeneous spaces

Let G₁⊂G be a closed subgroup of a locally compact group G and let X=G/G₁ be the quotient space of left cosets. Let X=(C₀(X),ΔX) be the corresponding G-C^∗-algebra where G=(C₀(G),Δ). Suppose that Γ is a closed abelian subgroup of G₁ and let Ψ be a 2-cocycle on the dual group . Let GΨ be the Rieffel deformation of G. Using the results of the previous paper of the author we may construct GΨ-C^∗-algebra XΨ - the Rieffel deformation of X. On the other hand we may perform the Rieffel deformation of the subgroup G₁ obtaining the closed quantum subgroup , which in turn, by the results of S. Vaes, leads to the GΨ-C^∗-algebra . In this paper we show that . We also consider the case where Γ⊂G is not a subgroup of G₁, for which we cannot construct the subgroup . Then generically XΨ cannot be identified with a quantum quotient. What may be shown is that it is a GΨ-simple object in the category of GΨ-C^∗-algebras.     

Total colorings and list total colorings of planar graphs without intersecting 4-cycles

Suppose that G is a planar graph with maximum degree Δ and without intersecting 4-cycles, that is, no two cycles of length 4 have a common vertex. Let χ^″(G), and denote the total chromatic number, list edge chromatic number and list total chromatic number of G, respectively. In this paper, it is proved that χ^″(G)=Δ+1 if Δ≥7, and and if Δ(G)≥8. Furthermore, if G is a graph embedded in a surface of nonnegative characteristic, then our results also hold.     

An application of Vizing and Vizing-like adjacency lemmas to Vizing’s Independence Number Conjecture of edge chromatic critical graphs

In 1968, Vizing conjectured that, if G is a Δ-critical graph with n vertices, then , where α(G) is the independence number of G. In this note, we apply Vizing and Vizing-like adjacency lemmas to this problem and obtain better bounds for Δ∈{7,…,19}.     

A result on the total colouring of powers of cycles

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. The Total Colouring Conjecture (TCC) states that for every simple graph G, χ_T(G)?Δ(G)+2. This work verifies the TCC for powers of cycles even and 2<k<n/2, showing that there exists and can be polynomially constructed a (Δ(G)+2)-total colouring for these graphs.     

On the average orders of the error term in the Dirichlet divisor problem

Let Δ(x) be the error term in the Dirichlet divisor problem. The purpose of this paper is to study the difference between two kinds of mean value formulas of Δ(x), that is, the mean value formulas and ∑_n?xΔ(n)^k with a natural number k. In particular we study the case k=2 and 3 in detail.     

Complete classification of torsion of elliptic curves over quadratic cyclotomic fields

Text

In a previous paper Najman (in press) [9], the author examined the possible torsions of an elliptic curve over the quadratic fields Q(i) and . Although all the possible torsions were found if the elliptic curve has rational coefficients, we were unable to eliminate some possibilities for the torsion if the elliptic curve has coefficients that are not rational. In this note, by finding all the points of two hyperelliptic curves over Q(i) and , we solve this problem completely and thus obtain a classification of all possible torsions of elliptic curves over Q(i) and .

Video

For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=VPhCkJTGB_o.     

Coloring the complements of intersection graphs of geometric figures

Let be the complement of the intersection graph G of a family of translations of a compact convex figure in Rⁿ. When n=2, we show that , where γ(G) is the size of the minimum dominating set of G. The bound on is sharp. For higher dimension we show that , for n?3. We also study the chromatic number of the complement of the intersection graph of homothetic copies of a fixed convex body in Rⁿ.     

(2,1)-Total labelling of outerplanar graphs

The (2,1)-total labelling number of a graph G is the width of the smallest range of integers that suffices to label the vertices and the edges of G such that no two adjacent vertices have the same label, no two adjacent edges have the same label and the difference between the labels of a vertex and its incident edges is at least 2. In this paper we prove that if G is an outerplanar graph with maximum degree Δ(G), then if Δ(G)?5, or Δ(G)=3 and G is 2-connected, or Δ(G)=4 and G contains no intersecting triangles.     

Upper bounds on the linear chromatic number of a graph

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is a union of vertex-disjoint paths. The linear chromatic number of G is the smallest number of colors in a linear coloring of G.Let G be a graph with maximum degree Δ(G). In this paper we prove the following results: (1) ; (2) if Δ(G)≤4; (3) if Δ(G)≤5; (4) if G is planar and Δ(G)≥52.     

Planar graphs without 5-cycles or without 6-cycles

Let G be a planar graph without 5-cycles or without 6-cycles. In this paper, we prove that if G is connected and δ(G)≥2, then there exists an edge xy∈E(G) such that d(x)+d(y)≤9, or there is a 2-alternating cycle. By using the above result, we obtain that (1) its linear 2-arboricity , (2) its list total chromatic number is Δ(G)+1 if Δ(G)≥8, and (3) its list edge chromatic number is Δ(G) if Δ(G)≥8.     

Decomposing oriented graphs into transitive tournaments

For an oriented graph G with n vertices, let f(G) denote the minimum number of transitive subtournaments that decompose G. We prove several results on f(G). In particular, if G is a tournament then and there are tournaments for which f(G)>n²/3000. For general G we prove that f(G)?⌊n²/3⌋ and this is tight. Some related parameters are also considered.