The strong chromatic index of a class of graphs

The strong chromatic index of a graph G is the minimum integer k such that the edge set of G can be partitioned into k induced matchings. Faudree et al. [R.J. Faudree, R.H. Schelp, A. Gyárfás, Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211] proposed an open problem: If G is bipartite and if for each edge xy∈E(G), d(x)+d(y)≤5, then sχ^′(G)≤6. Let H₀ be the graph obtained from a 5-cycle by adding a new vertex and joining it to two nonadjacent vertices of the 5-cycle. In this paper, we show that if G (not necessarily bipartite) is not isomorphic to H₀ and d(x)+d(y)≤5 for any edge xy of G then sχ^′(G)≤6. The proof of the result implies a linear time algorithm to produce a strong edge coloring using at most 6 colors for such graphs.     

Local condition for planar graphs of maximum degree 7 to be 8-totally colorable

The total chromatic number of a graph G, denoted by χ^″(G), is the minimum number of colors needed to color the vertices and edges of G such that no two adjacent or incident elements get the same color. It is known that if a planar graph G has maximum degree Δ≥9, then χ^″(G)=Δ+1. In this paper, we prove that if G is a planar graph with maximum degree 7, and for every vertex v, there is an integer k_v∈{3,4,5,6} so that v is not incident with any k_v-cycle, then χ^″(G)=8.     

Colorings at minimum cost

We define by min_c∑_{u,v}∈E(G)|c(u)−c(v)| the min-costMC(G) of a graph G, where the minimum is taken over all proper colorings c. The min-cost-chromatic numberχ_M(G) is then defined to be the (smallest) number of colors k for which there exists a proper k-coloring c attaining MC(G). We give constructions of graphs G where χ(G) is arbitrarily smaller than χ_M(G). On the other hand, we prove that for every 3-regular graph G^′, χ_M(G^′)≤4 and for every 4-regular line graph G^″, χ_M(G^″)≤5. Moreover, we show that the decision problem whether χ_M(G)=k is -hard for k≥3.     

On Vizing’s bound for the chromatic index of a multigraph

Two of the basic results on edge coloring are Vizing’s Theorem [V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25-30 (in Russian); V.G. Vizing, The chromatic class of a multigraph, Kibernetika (Kiev) 3 (1965) 29-39 (in Russian). English translation in Cybernetics 1 32-41], which states that the chromatic index χ^′(G) of a (multi)graph G with maximum degree Δ(G) and maximum multiplicity μ(G) satisfies Δ(G)≤χ^′(G)≤Δ(G)+μ(G), and Holyer’s Theorem [I. Holyer, The NP-completeness of edge-colouring, SIAM J. Comput. 10 (1981) 718-720], which states that the problem of determining the chromatic index of even a simple graph is NP-hard. Hence, a good characterization of those graphs for which Vizing’s upper bound is attained seems to be unlikely. On the other hand, Vizing noticed in the first two above-cited references that the upper bound cannot be attained if Δ(G)=2μ(G)+1≥5. In this paper we discuss the problem: For which values Δ,μ does there exist a graph G satisfying Δ(G)=Δ, μ(G)=μ, and χ^′(G)=Δ+μ.     

Improved bounds on acyclic edge colouring

We prove that the acyclic chromatic index a^′(G)?6Δ for all graphs with girth at least 9. We extend the same method to obtain a bound of 4.52Δ with the girth requirement g?220. We also obtain a relationship between g and a^′(G).     

Probability that the commutator of two group elements is equal to a given element

In this paper we study the probability that the commutator of two randomly chosen elements in a finite group is equal to a given element of that group. Explicit computations are obtained for groups G which |G^′| is prime and G^′≤Z(G) as well as for groups G which |G^′| is prime and G^′∩Z(G)=1. This paper extends results of Rusin [see D.J. Rusin, What is the probability that two elements of a finite group commute? Pacific J. Math. 82 (1) (1979) 237-247].     

On the supremum of the pseudocompact group topologies

P is the class of pseudocompact Hausdorff topological groups, and P^′ is the class of groups which admit a topology T such that (G,T)∈P. It is known that every G=(G,T)∈P is totally bounded, so for G∈P^′ the supremum T^∨(G) of all pseudocompact group topologies on G and the supremum T#(G) of all totally bounded group topologies on G satisfy T^∨⊆T#.The authors conjecture for abelian G∈P^′ that T^∨=T#. That equality is established here for abelian G∈P^′ with any of these (overlapping) properties. (a) G is a torsion group; (b) |G|?c²; (c) r₀(G)=|G|=ω|G|; (d) |G| is a strong limit cardinal, and r₀(G)=|G|; (e) some topology T with (G,T)∈P satisfies w(G,T)?c; (f) some pseudocompact group topology on G is metrizable; (g) G admits a compact group topology, and r₀(G)=|G|. Furthermore, the product of finitely many abelian G∈P^′, each with the property T^∨(G)=T#(G), has the same property.     

Paired bondage in trees

Let G=(V,E) be a graph with δ(G)≥1. A set D⊆V is a paired dominating set if D is dominating, and the induced subgraph 〈D〉 contains a perfect matching. The paired domination number of G, denoted by γ_p(G), is the minimum cardinality of a paired dominating set of G. The paired bondage number, denoted by b_p(G), is the minimum cardinality among all sets of edges E^′⊆E such that δ(G−E^′)≥1 and γ_p(G−E^′)>γ_p(G). We say that G is a γ_p-strongly stable graph if, for all E^′⊆E, either γ_p(G−E^′)=γ_p(G) or δ(G−E^′)=0. We discuss the basic properties of paired bondage and give a constructive characterization of γ_p-strongly stable trees.     

Sur le changement de base stable des intégrales orbitales pondérées

Let G^′ be a quasi-split connected reductive group over a p-adic field F. Let E be a cyclic extension of F. In the context of cyclic base change, we can attach to G^′ and E a twisted space G^* (in the sense of Labesse). Let G be an inner form of G^*. If G^′ is GL(n), SL(n) or more generally a group which we call L-stable, we define and prove the existence of a non-invariant transfer between the weighted orbital integrals of G and those of G^′. For GL(n), such a transfer has been conjectured by Labesse. The proof is based on previous results of harmonic analysis on Lie algebras and on a generalization of a result of Waldspurger concerning Arthur's (G,M)-families.     

Connectivity of the Mycielskian of a graph

In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph μ(G), which is called the Mycielskian of G. This paper investigates the vertex-connectivity κ(μ(G)) and edge-connectivity κ^′(μ(G)) of μ(G) . We show that κ(μ(G))=min{δ(μ(G)),2κ(G)+1} and κ^′(μ(G))=δ(μ(G)).     

Vertex-, edge-, and total-colorings of Sierpiński-like graphs

Vertex-colorings, edge-colorings and total-colorings of the Sierpiński gasket graphs S_n, the Sierpiński graphs S(n,k), graphs S⁺(n,k), and graphs S⁺⁺(n,k) are considered. In particular, χ^″(S_n), χ^′(S(n,k)), χ(S⁺(n,k)), χ(S⁺⁺(n,k)), χ^′(S⁺(n,k)), and χ^′(S⁺⁺(n,k)) are determined.     

The first order definability of graphs: Upper bounds for quantifier depth

Let D(G) denote the minimum quantifier depth of a first order sentence that defines a graph G up to isomorphism in terms of the adjacency and equality relations. Call two vertices of G similar if they have the same adjacency to any other vertex and denote the maximum number of pairwise similar vertices in G by σ(G). We prove that σ(G)+1?D(G)?max{σ(G)+2,(n+5)/2}, where n denotes the number of vertices of G. In particular, D(G)?(n+5)/2 for every G with no transposition in the automorphism group. If G is connected and has maximum degree d, we prove that for a constant . A linear lower bound for graphs of maximum degree 3 with no transposition in the automorphism group follows from an earlier result by Cai, Fürer, and Immerman [An optimal lower bound on the number of variables for graph identification, Combinatorica 12(4) (1992) 389-410]. Our upper bounds for D(G) hold true even if we allow only definitions with at most one alternation in any sequence of nested quantifiers.In passing we establish an upper bound for a related number D(G,G^′), the minimum quantifier depth of a first order sentence which is true on exactly one of graphs G and G^′. If G and G^′ are non-isomorphic and both have n vertices, then D(G,G^′)?(n+3)/2. This bound is tight up to an additive constant of 1. If we additionally require that a sentence distinguishing G and G^′ is existential, we prove only a slightly weaker bound D(G,G^′)?(n+5)/2.     

Hamiltonicity and pancyclicity of cartesian products of graphs

The cartesian product of a graph G with K₂ is called a prism over G. We extend known conditions for hamiltonicity and pancyclicity of the prism over a graph G to the cartesian product of G with paths, cycles, cliques and general graphs. In particular we give results involving cubic graphs and almost claw-free graphs.We also prove the following: Let G and H be two connected graphs. Let both G and H have a 2-factor. If Δ(G)≤g^′(H) and Δ(H)≤g^′(G) (we denote by g^′(F) the length of a shortest cycle in a 2-factor of a graph F taken over all 2-factorization of F), then G□H is hamiltonian.     

Regular graphs are not universal fixers

For any permutation π of the vertex set of a graph G, the graph πG is obtained from two copies G^′ and G^″ of G by joining u∈V(G^′) and v∈V(G^″) if and only if v=π(u). Denote the domination number of G by γ(G). For all permutations π of V(G), γ(G)≤γ(πG)≤2γ(G). If γ(πG)=γ(G) for all π, then G is called a universal fixer. We prove that regular graphs and graphs with γ=4 are not universal fixers.     

Bipartite graphs are not universal fixers

For any permutation π of the vertex set of a graph G, the graph πG is obtained from two copies G^′ and G^″ of G by joining u∈V(G^′) and v∈V(G^″) if and only if v=π(u). Denote the domination number of G by γ(G). For all permutations π of V(G), γ(G)≤γ(πG)≤2γ(G). If γ(πG)=γ(G) for all π, then G is called a universal fixer. We prove that graphs without 5-cycles are not universal fixers, from which it follows that bipartite graphs are not universal fixers.     

Independence and coloring properties of direct products of some vertex-transitive graphs

Let α(G) and χ(G) denote the independence number and chromatic number of a graph G, respectively. Let G×H be the direct product graph of graphs G and H. We show that if G and H are circular graphs, Kneser graphs, or powers of cycles, then α(G×H)=max{α(G)|V(H)|,α(H)|V(G)|} and χ(G×H)=min{χ(G),χ(H)}.     

On a conjecture of E. Rapaport Strasser about knot-like groups and its pro-p version

A group G is knot-like if it is finitely presented of deficiency 1 and has abelianization G/G^′?Z. We prove the conjecture of E. Rapaport Strasser that if a knot-like group G has a finitely generated commutator subgroup G^′ then G^′ should be free in the special case when the commutator G^′ is residually finite. It is a corollary of a much more general result : if G is a discrete group of geometric dimension n with a finite K(G,1)-complex Y of dimension n, Y has Euler characteristics 0, N is a normal residually finite subgroup of G, N is of homological type FP_n-1 and G/N?Z then N is of homological type FP_n and hence G/N has finite virtual cohomological dimension vcd(G/N)=cd(G)-cd(N). In particular either N has finite index in G or cd(N)?cd(G)-1.Furthermore we show a pro-p version of the above result with the weaker assumption that G/N is a pro-p group of finite rank. Consequently a pro-p version of Rapaport's conjecture holds.     

Matroids over fp which are rational excluded minors

For a given prime p, we construct a collection of 2^p matroids G_p,a with (1) χ_pf(G_p,a)={p}, and (2) G_p,a is an excluded minor for rational representability. The motivating construction (Section 2) disproves a conjectures of Reid [4], using relatively high-rank, high cardinality matroids. The general construction (Section 3) makes use of ordered partitions (χ_pf(G) denotes the prime-field characteristic set of G, i.e., the set of prime fields over which G may be represented, while G can be represented over fields of no other characteristic.) Finally, Section 4 offers another construction with the same properties–a kind of projective dual to Section 2.