Orientable Hamilton Cycle Embeddings of Complete Tripartite Graphs II: Voltage Graph Constructions and Applications

In an earlier article the authors constructed a hamilton cycle embedding of in a nonorientable surface for all and then used these embeddings to determine the genus of some large families of graphs. In this two‐part series, we extend those results to orientable surfaces for all . In part II, a voltage graph construction is presented for building embeddings of the complete tripartite graph on an orientable surface such that the boundary of every face is a hamilton cycle. This construction works for all such that p is prime, completing the proof started by part I (which covers the case ) that there exists an orientable hamilton cycle embedding of for all , . These embeddings are then used to determine the genus of several families of graphs, notably for and, in some cases, for .     

Improper Coloring of Sparse Graphs with a Given Girth,II: Constructions

A graph G is ‐colorable if can be partitioned into two sets and so that the maximum degree of is at most j and of is at most k. While the problem of verifying whether a graph is (0, 0)‐colorable is easy, the similar problem with in place of (0, 0) is NP‐complete for all nonnegative j and k with . Let denote the supremum of all x such that for some constant every graph G with girth g and for every is ‐colorable. It was proved recently that . In a companion paper, we find the exact value . In this article, we show that increasing g from 5 further on does not increase much. Our constructions show that for every g, . We also find exact values of for all g and all .     

The Images of the Clique Operator and Its Square are Different

Let be the class of all graphs and K be the clique operator. The validity of the equality has been an open question for several years. A graph in but not in is exhibited here.     

Biembedding a Steiner Triple System With a Hamilton Cycle Decomposition of a Complete Graph

We construct a face two‐colourable, blue and green say, embedding of the complete graph in a nonorientable surface in which there are blue faces each of which have a hamilton cycle as their facial walk and green faces each of which have a triangle as their facial walk; equivalently a biembedding of a Steiner triple system of order n with a hamilton cycle decomposition of , for all and . Using a variant of this construction, we establish the minimum genus of nonorientable embeddings of the graph , for where and .     

Minors in ‐ Chromatic Graphs,II

Let denote the graph obtained from the complete graph by deleting the edges of some ‐subgraph. The author proved earlier that for each fixed s and , every graph with chromatic number has a minor. This confirmed a partial case of the corresponding conjecture by Woodall and Seymour. In this paper, we show that the statement holds already for much smaller t, namely, for .     

Generating Nonisomorphic Quadrangular Embeddings of a Complete Graph

We construct (resp. ) index one current graphs with current group such that the current graphs have different underlying graphs and generate nonisomorphic orientable (resp. nonorientable) quadrangular embeddings of the complete graph , (resp. ).     

Multicolor Ramsey Numbers For Complete Bipartite Versus Complete Graphs

Let be graphs. The multicolor Ramsey number is the minimum integer r such that in every edge‐coloring of by k colors, there is a monochromatic copy of in color i for some . In this paper, we investigate the multicolor Ramsey number , determining the asymptotic behavior up to a polylogarithmic factor for almost all ranges of t and m. Several different constructions are used for the lower bounds, including the random graph and explicit graphs built from finite fields. A technique of Alon and Rödl using the probabilistic method and spectral arguments is employed to supply tight lower bounds. A sample result is for any t and m, where c₁ and c₂ are absolute constants.     

Circular Chromatic Indices of Regular Graphs

The circular chromatic index of a graph G, written , is the minimum r permitting a function such that whenever e and are adjacent. It is known that for any , there is a 3‐regular simple graph G with . This article proves the following results: Assume is an odd integer. For any , there is an n‐regular simple graph G with . For any , there is an n‐regular multigraph G with .     

A Combined Logarithmic Bound on the Chromatic Index of Multigraphs

For a multigraph G, the integer round‐up of the fractional chromatic index provides a good general lower bound for the chromatic index . For an upper bound, Kahn 1996 showed that for any real there exists a positive integer N so that whenever . We show that for any multigraph G with order n and at least one edge, ). This gives the following natural generalization of Kahn's result: for any positive reals , there exists a positive integer N so that + c whenever . We also compare the upper bound found here to other leading upper bounds.     

Face 2‐Colorable Embeddings with Faces of Specified Lengths

Suppose and are arbitrary lists of positive integers. In this article, we determine necessary and sufficient conditions on M and N for the existence of a simple graph G, which admits a face 2‐colorable planar embedding in which the faces of one color have boundary lengths and the faces of the other color have boundary lengths . Such a graph is said to have a planar ‐biembedding. We also determine necessary and sufficient conditions on M and N for the existence of a simple graph G whose edge set can be partitioned into r cycles of lengths and also into t cycles of lengths . Such a graph is said to be ‐decomposable.     

Total Vertex Irregularity Strength of Dense Graphs

Consider a graph of minimum degree δ and order n. Its total vertex irregularity strength is the smallest integer k for which one can find a weighting such that for every pair of vertices of G. We prove that the total vertex irregularity strength of graphs with is bounded from above by . One of the cornerstones of the proof is a random ordering of the vertices generated by order statistics.     

Large ‐ or ‐Minors in 3‐Connected Graphs

There are numerous results bounding the circumference of certain 3‐connected graphs. There is no good bound on the size of the largest bond (cocircuit) of a 3‐connected graph, however. Oporowski, Oxley, and Thomas (J Combin Theory Ser B 57 (1993), 2, 239–257) proved the following result in 1993. For every positive integer k, there is an integer such that every 3‐connected graph with at least n vertices contains a ‐ or ‐minor. This result implies that the size of the largest bond in a 3‐connected graph grows with the order of the graph. Oporowski et al. obtained a huge function iteratively. In this article, we first improve the above authors' result and provide a significantly smaller and simpler function . We then use the result to obtain a lower bound for the largest bond of a 3‐connected graph by showing that any 3‐connected graph on n vertices has a bond of size at least . In addition, we show the following: Let G be a 3‐connected planar or cubic graph on n vertices. Then for any , G has a ‐minor with , and thus a bond of size at least .     

Minimum Vertex Degree Threshold for ‐tiling*

We prove that the vertex degree threshold for tiling (the 3‐uniform hypergraph with four vertices and two triples) in a 3‐uniform hypergraph on vertices is , where if and otherwise. This result is best possible, and is one of the first results on vertex degree conditions for hypergraph tiling.     

Two‐sided Group Digraphs and Graphs

We study a family of digraphs (directed graphs) that generalises the class of Cayley digraphs. For nonempty subsets of a group G, we define the two‐sided group digraph to have vertex set G, and an arc from x to y if and only if for some and . In common with Cayley graphs and digraphs, two‐sided group digraphs may be useful to model networks as the same routing and communication scheme can be implemented at each vertex. We determine necessary and sufficient conditions on L and R under which may be viewed as a simple graph of valency , and we call such graphs two‐sided group graphs. We also give sufficient conditions for two‐sided group digraphs to be connected, vertex‐transitive, or Cayley graphs. Several open problems are posed. Many examples are given, including one on 12 vertices with connected components of sizes 4 and 8.     

Saturation numbers for families of graph subdivisions

For a family of graphs, a graph G is ‐saturated if G contains no member of as a subgraph, but for any edge in , contains some member of as a subgraph. The minimum number of edges in an ‐saturated graph of order n is denoted . A subdivision of a graph H, or an H‐subdivision, is a graph G obtained from H by replacing the edges of H with internally disjoint paths of arbitrary length. We let denote the family of H‐subdivisions, including H itself. In this paper, we study when H is one of or , obtaining several exact results and bounds. In particular, we determine exactly for and show for n sufficiently large that there exists a constant such that . For we show that will suffice, and that this can be improved slightly depending on the value of . We also give an upper bound on for all t and show that . This provides an interesting contrast to a 1937 result of Wagner (Math Ann, 114 (1937), 570–590), who showed that edge‐maximal graphs without a K₅‐minor have at least edges.     

Stability of Hereditary Graph Classes Under Closure Operations

If is a subclass of the class of claw‐free graphs, then is said to be stable if, for any , the local completion of G at any vertex is also in . If is a closure operation that turns a claw‐free graph into a line graph by a series of local completions and is stable, then for any . In this article, we study stability of hereditary classes of claw‐free graphs defined in terms of a family of connected closed forbidden subgraphs. We characterize line graph preimages of graphs in families that yield stable classes, we identify minimal families that yield stable classes in the finite case, and we also give a general background for techniques for handling unstable classes by proving that their closure may be included into another (possibly stable) class.     

On the Multichromatic Number of s‐Stable Kneser Graphs

For positive integers n and s, a subset [n] is s‐stable if for distinct . The s‐stable r‐uniform Kneser hypergraph is the r‐uniform hypergraph that has the collection of all s‐stable k‐element subsets of [n] as vertex set and whose edges are formed by the r‐tuples of disjoint s‐stable k‐element subsets of [n]. Meunier ( 21 ) conjectured that for positive integers with , and , the chromatic number of s‐stable r ‐uniform Kneser hypergraphs is equal to . It is a generalized version of the conjecture proposed by Alon et al. ( 1 ). Alon et al. ( 1 ) confirmed Meunier's conjecture for with arbitrary positive integer q. Lin et al. ( 17 ) studied the kth chromatic number of the Mycielskian of the ordinary Kneser graphs for . They conjectured that for . The case was proved by Mycielski ( 22 ). Lin et al. ( 17 ) confirmed their conjecture for , or when n is a multiple of k or . In this paper, we investigate the multichromatic number of the usual s ‐stable Kneser graphs . With the help of Fan's (1952) combinatorial lemma, we show that Meunier's conjecture is true for r is a power of 2 and s is a multiple of r, and Lin‐Liu‐Zhu's conjecture is true for .     

Transversals in Trees

The total embedding polynomial of a graph G is the bivariate polynomial where is the number of embeddings, for into the orientable surface , and is the number of embeddings, for into the nonorientable surface . The sequence is called the total embedding distribution of the graph G; it is known for relatively few classes of graphs, compared to the genus distribution . The circular ladder graph is the Cartesian product of the complete graph on two vertices and the cycle graph on n vertices. In this article, we derive a closed formula for the total embedding distribution of circular ladders.     

Eigenvalues of ‐Free Graphs and the Connectivity of Their Independence Complexes

Let G be a graph on n vertices, with maximal degree d, and not containing as an induced subgraph. We prove:

• 1.
• 2.

Here is the maximal eigenvalue of the Laplacian of G, is the independence complex of G, and denotes the topological connectivity of a complex plus 2. These results provide improved bounds for the existence of independent transversals in ‐free graphs.     

Anti‐Ramsey Problems for t Edge‐Disjoint Rainbow Spanning Subgraphs: Cycles,Matchings, or Trees

We seek the maximum number of colors in an edge‐coloring of the complete graph not having t edge‐disjoint rainbow spanning subgraphs of specified types. Let , , and denote the answers when the spanning subgraphs are cycles, matchings, or trees, respectively. We prove for and for . We prove for and for . We also provide constructions for the more general problem in which colorings are restricted so that colors do not appear on more than q edges at a vertex.