Random regular graphs of high degree

Random d‐regular graphs have been well studied when d is fixed and the number of vertices goes to infinity. We obtain results on many of the properties of a random d‐regular graph when d=d(n) grows more quickly than . These properties include connectivity, hamiltonicity, independent set size, chromatic number, choice number, and the size of the second eigenvalue, among others. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 346–363, 2001.     

Distance degree regular graphs

In this note, inequalities between the distance degrees of distance degree regular graphs and to characterize the graphs when one of the equalities holds are proved.     

The total chromatic number of regular graphs of high degree

The total chromatic number χT (G) of a graph G is the minimum number of colors needed to color the edges and the vertices of G so that incident or adjacent elements have distinct colors. We show that if G is a regular graph and d(G) 32 |V (G)| + 263 , where d(G) denotes the degree of a vertex in G, then χT (G) d(G) + 2.     

The total chromatic number of regular graphs of even order and high degree

The total chromatic number χ_T(G) of a graph G is the minimum number of colours needed to colour the edges and the vertices of G so that incident or adjacent elements have distinct colours. We show that if G is a regular graph of even order and , thenχ_T(G)Δ(G)+2.     

Quotients of connected regular graphs of even degree

This paper introduces a method of listing all nonequivalent quotients of any connected regular graph of even degree with a given 2-factorization. The method is based on the characterization of connected 2d-regular graphs as Schreier coset graphs given by Gross (J. Combin. Theory Ser. B22 (1977), 227–232). Various representations of a given graph with a fixed 2-factorization are also investigated. The work is related to graph imbedding theory, particularly to voltage and current graphs.     

Generating all planer graphs regular of degree four

All planar connected graphs regular of degree four can be generated from the graph of the octahedron, using four operations.     

An application of Tutte’s Theorem to 1-factorization of regular graphs of high degree

A well known conjecture in graph theory states that every regular graph of even order 2n and degree λ(2n), where λ≥1/2, is 1-factorizable. Chetwynd and Hilton [A.G. Chetwynd, A.J.W. Hilton, 1-factorizing regular graphs of high degree — An improved bound, Discrete Math. 75 (1989) 103-112] and, independently, Niessen and Volkmann [T. Niessen, L. Volkmann, Class 1 conditions depending on the minimum degree and the number of vertices of maximum degree, J. Graph Theory (2) 14 (1990) 225-246] proved the above conjecture under the assumption that . Since these results were published no significant or even partial improvement has been made in terms of lowering the bound on λ. We shall obtain here a partial improvement on λ. Specifically, using the original Chetwynd-Hilton approach and Tutte’s 1-Factor Theorem, we show that the above bound can be improved to , apart (possibly) from two families of exceptional cases. We then show, under the stronger assumption that λ≥λ^∗≈0.785, that one of the two families of exceptional cases cannot occur.     

Regular graphs with high edge degree

For any vertex x of a graph G let Δ(x) denote the set of vertices adjacent to x. We seek to describe the connected graphs G which are regular of valence n and in which for all adjacent vertices x and y |Δ(x) ∩ Δ(y)| = n ? 1 ? s. It is known that the complete graphs are the graphs for which s = 0. For any s, any complete many-partite graph, each part containing s + 1 vertices, is such a graph. We show that these are the only such graphs for which the valence exceeds 2s² ? s + 1. The graphs satisfying these conditions for s = 1 or 2 are characterized (up to the class of trivalent triangle-free graphs.)     

Edge-coloring critical graphs with high degree

It is proved here that any edge-coloring critical graph of order n and maximum degree Δ?8 has the size at least 3(n+Δ−8). It generalizes a result of Hugh Hind and Yue Zhao.     

Recursive constructions of small regular graphs of given degree and girth

We revisit and generalize a recursive construction due to Sachs involving two graphs which increases the girth of one graph and the degree of the other. We investigate the properties of the resulting graphs in the context of cages and construct families of small graphs using geometric graphs, Paley graphs, and techniques from the theory of Cayley maps.     

Random regular graphs of non-constant degree: Concentration of the chromatic number

In this work we show that with high probability the chromatic number of a graph sampled from the random regular graph model G_n,d for d=o(n^1/5) is concentrated in two consecutive values, thus extending a previous result of Achlioptas and Moore. This concentration phenomena is very similar to that of the binomial random graph model G(n,p) with . Our proof is largely based on ideas of Alon and Krivelevich who proved this two-point concentration result for G(n,p) for p=n^−δ where δ>1/2. The main tool used to derive such a result is a careful analysis of the distribution of edges in G_n,d, relying both on the switching technique and on bounding the probability of exponentially small events in the configuration model.     

On 4-chromatic edge-critical regular graphs of high connectivity

New examples of 4-chromatic edge-critical r-regular and r-connected graphs are presented for r = 6,8,10.     

Overfull conjecture for graphs with high minimum degree

Chetwynd and Hilton showed that any regular graph G of even order n which has relatively high degree has a 1‐factorization. This is equivalent to saying that under these conditions G has chromatic index equal to its maximum degree . Using this result, we show that any (not necessarily regular) graph G of even order n that has sufficiently high minimum degree has chromatic index equal to its maximum degree providing that G does not contain an “overfull” subgraph, that is, a subgraph which trivially forces the chromatic index to be more than the maximum degree. This result thus verifies the Overfull Conjecture for graphs of even order and sufficiently high minimum degree. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 73–80, 2004     

Factorizations of complete multipartite graphs into generalized cubes

For a positive integer d, the usual d‐dimensional cube Q_d is defined to be the graph (K₂)^d, the Cartesian product of d copies of K₂. We define the generalized cube Q(K_k, d) to be the graph (K_k)^d for positive integers d and k. We investigate the decomposition of the complete multipartite graph K into factors that are vertex‐disjoint unions of generalized cubes Q(K_k, d_i), where k is a power of a prime, n and j are positive integers with j ≤ n, and the d_i may be different in different factors. We also use these results to partially settle a problem of Kotzig on Q_d‐factorizations of K_n. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 144–150, 2000     

1‐Factorizations of pseudorandom graphs

A 1‐factorization of a graph G is a collection of edge‐disjoint perfect matchings whose union is E(G). In this paper, we prove that for any ?>0, an (n,d,λ)‐graph G admits a 1‐factorization provided that n is even, C₀ ≤ d ≤ n?1 (where C₀=C₀(?) is a constant depending only on ?), and λ ≤ d^1??. In particular, since (as is well known) a typical random d‐regular graph G_n,d is such a graph, we obtain the existence of a 1‐factorization in a typical G_n,d for all C₀ ≤ d ≤ n?1, thereby extending to all possible values of d results obtained by Janson, and independently by Molloy, Robalewska, Robinson, and Wormald for fixed d. Moreover, we also obtain a lower bound for the number of distinct 1‐factorizations of such graphs G, which is better by a factor of 2^nd/2 than the previously best known lower bounds, even in the simplest case where G is the complete graph.