n-Tuple Coloring of Planar Graphs with Large Odd Girth

 The main result of the papzer is that any planar graph with odd girth at least 10k−7 has a homomorphism to the Kneser graph G _k ^{2 k +1}, i.e. each vertex can be colored with k colors from the set {1,2,…,2k+1} so that adjacent vertices have no colors in common. Thus, for example, if the odd girth of a planar graph is at least 13, then the graph has a homomorphism to G ₂ ⁵, also known as the Petersen graph. Other similar results for planar graphs are also obtained with better bounds and additional restrictions. Received: June 14, 1999 Final version received: July 5, 2000     

Independence and graph homomorphisms graph homomorphisms

A graph with n vertices that contains no triangle and no 5-cycle and minimum degree exceeding n/4 contains an independent set with at least (3n)/7 vertices. This is best possible. The proof proceeds by producing a homomorphism to the 7-cycle and invoking the No Homomorphism Lemma. For k ≥ 4, a graph with n vertices, odd girth 2k+1, and minimum degree exceeding n/(k+1) contains an independent set with at least kn/(2k+1) vertices; however, we suspect this is not best possible. © 1993 John Wiley & Sons, Inc.     

A family of regular graphs of girth 5

Murty [A generalization of the Hoffman-Singleton graph, Ars Combin. 7 (1979) 191-193.] constructed a family of (p^m+2)-regular graphs of girth five and order 2p^2m, where p?5 is a prime, which includes the Hoffman-Singleton graph [A.J. Hoffman, R.R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. (1960) 497-504]. This construction gives an upper bound for the least number f(k) of vertices of a k-regular graph with girth 5. In this paper, we extend the Murty construction to k-regular graphs with girth 5, for each k. In particular, we obtain new upper bounds for f(k), k?16.     

Finding small regular graphs of girths 6, 8 and 12 as subgraphs of cages

Small k-regular graphs of girth g where g=6,8,12 are obtained as subgraphs of minimal cages. More precisely, we obtain (k,6)-graphs on 2(kq−1) vertices, (k,8)-graphs on 2k(q²−1) vertices and (k,12)-graphs on 2kq²(q²−1), where q is a prime power and k is a positive integer such that q≥k≥3. Some of these graphs have the smallest number of vertices known so far among the regular graphs with girth g=6,8,12.     

Subgroup-Chain Graphs

Starting from chains of subgroups in a group a construction for k-regular graphs is given and as an application of this construction a cubic graph of girth 20 with 6072 vertices is produced. This graph is exceptional in that, at the time of writing, it has fewest vertices for a cubic graph of this girth.     

On the Number of Edges in Colour-Critical Graphs and Hypergraphs

A (hyper)graph G is called k-critical if it has chromatic number k, but every proper sub(hyper)graph of it is (k-1)-colourable. We prove that for sufficiently large k, every k-critical triangle-free graph on n vertices has at least (k-o(k))n edges. Furthermore, we show that every (k+1)-critical hypergraph on n vertices and without graph edges has at least (k-3/³?{k}) n(k-3/\sqrt[3]{k}) n edges. Both bounds differ from the best possible bounds by o(kn) even for graphs or hypergraphs of arbitrary girth.     

On Narrow Hexagonal Graphs with a 3-Homogeneous Suborbit

A connected graph of girth m 3 is called a polygonal graph if it contains a set of m-gons such that every path of length two is contained in a unique element of the set. In this paper we investigate polygonal graphs of girth 6 or more having automorphism groups which are transitive on the vertices and such that the vertex stabilizers are 3-homogeneous on adjacent vertices. We previously showed that the study of such graphs divides naturally into a number of substantial subcases. Here we analyze one of these cases and characterize the k-valent polygonal graphs of girth 6 which have automorphism groups transitive on vertices, which preserve the set of special hexagons, and which have a suborbit of size k – 1 at distance three from a given vertex.     

A smallest graph of girth 5 and valency 5

We give a graph of girth 5 and valency 5 having 30 vertices. It is shown that this is the minimum number of vertices. Further we construct graphs of girth 5 and valency p (p a prime ≥ 3) having 2p² ? 2p vertices.     

Regular graphs constructed from the classical generalized quadrangle Q(4, q)

Let c_k be the smallest number of vertices in a regular graph with valency k and girth 8. It is known that c_{k + 1}?2(1 + k + k² + k³) with equality if and only if there exists a finite generalized quadrangle of order k. No such quadrangle is known when k is not a prime power. In this case, small regular graphs of valency k + 1 and girth 8 can be constructed from known generalized quadrangles of order q>k by removing a part of its structure. We investigate the case when q = k + 1 is a prime power, and try to determine the smallest graph under consideration that can be constructed from a generalized quadrangle of order q. This problem appears to be much more difficult than expected. We have general bounds and improve these for the classical generalized quadrangle Q(4, q), q even. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:70‐83, 2010     

Contractible edges in triangle-free graphs

An edge of a graph is calledk-contractible if the contraction of the edge results in ak-connected graph. Thomassen [5] proved that everyk-connected graph of girth at least four has ak-contractible edge. In this paper, we study the distribution ofk-contractible edges in triangle-free graphs and show the following: Whenk≧2, everyk-connected graph of girth at least four and ordern≧3k, hasn+(3/2)k ²-3k or morek-contractible edges.     

Up-Embeddability of a Graph by Order and Girth

Let G be a connected graph of order n and girth g. If d_G(u) + d_G(v) ≥ n − 2g + 5 for any two non-adjacent vertices u and v, then G is up-embeddable. Further more, the lower bound is best possible. Similarly the result of k-edge connected simple graph with girth g is also obtained, k = 2,3. Partially supported by the Postdoctoral Seience Foundation of Central South University and NNSFC under Grant No. 10751013.     

Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k

A graph G is (k,0)‐colorable if its vertices can be partitioned into subsets V₁ and V₂ such that in G[V₁] every vertex has degree at most k, while G[V₂] is edgeless. For every integer k?0, we prove that every graph with the maximum average degree smaller than (3k+4)/(k+2) is (k,0)‐colorable. In particular, it follows that every planar graph with girth at least 7 is (8, 0)‐colorable. On the other hand, we construct planar graphs with girth 6 that are not (k,0)‐colorable for arbitrarily large k. © 2009 Wiley Periodicals, Inc. J Graph Theory 65:83–93, 2010     

Completions of Goldschmidt Amalgams of Type G4 in Dimension 3

The subgroups of GL₃(k) which are completions of the Goldschmidt G ₄-amalgam are determined. We also draw attention to five related graphs which are remarkable in that they have large girth and few vertices.     

Automorphisms of random graphs with specified vertices

Conditions are found under which the expected number of automorphisms of a large random labelled graph with a given degree sequence is close to 1. These conditions involve the probability that such a graph has a given subgraph. One implication is that the probability that a random unlabelledk-regular simple graph onn vertices has only the trivial group of automorphisms is asymptotic to 1 asn → ∞ with 3≦k=O(n ^1/2−c). In combination with previously known results, this produces an asymptotic formula for the number of unlabelledk-regular simple graphs onn vertices, as well as various asymptotic results on the probable connectivity and girth of such graphs. Corresponding results for graphs with more arbitrary degree sequences are obtained. The main results apply equally well to graphs in which multiple edges and loops are permitted, and also to bicoloured graphs. Research of the second author supported by U. S. National Science Foundation Grant MCS-8101555, and by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowships Scheme. Current address: Mathematics Department, University of Auckland, Auckland, New Zealand.     

Sparse <Emphasis Type="Italic">H</Emphasis>-Colourable Graphs of Bounded Maximum Degree

Let F be a graph of order at most k. We prove that for any integer g there is a graph G of girth at least g and of maximum degree at most 5k¹³ such that G admits a surjective homomorphism c to F, and moreover, for any F-pointed graph H with at most k vertices, and for any homomorphism h from G to H there is a unique homomorphism f from F to H such that h=fc. As a consequence, we prove that if H is a projective graph of order k, then for any finite family of prescribed mappings from a set X to V(H) (with ||=t), there is a graph G of arbitrary large girth and of maximum degree at most 5k^26mt (where m=|X|) such that and up to an automorphism of H, there are exactly t homomorphisms from G to H, each of which is an extension of an f.Supported in part by the National Science Council under grant NSC89-2115-M-110-012Final version received: June 9, 2003     

The Erd s-Sós conjecture for graphs of girth 5

We prove that every graph of girth at least 5 with minimum degree δ k/2 contains every tree with k edges, whose maximum degree does not exceed the maximum degree of the graph. An immediate consequence is that the famous Erd s-Sós Conjecture, saying that every graph of order n with more than n(k − 1)/2 edges contains every tree with k edges, is true for graphs of girth at least 5.     

Looseness of Plane Graphs

A face of a vertex coloured plane graph is called loose if the number of colours used on its vertices is at least three. The looseness of a plane graph G is the minimum k such that any surjective k-colouring involves a loose face. In this paper we prove that the looseness of a connected plane graph G equals the maximum number of vertex disjoint cycles in the dual graph G* increased by 2. We also show upper bounds on the looseness of graphs based on the number of vertices, the edge connectivity, and the girth of the dual graphs. These bounds improve the result of Negami for the looseness of plane triangulations. We also present infinite classes of graphs where the equalities are attained.     

Twelve general position points always form three intersecting tetrahedra

A g cage of valency k is a regular graph of girth g and valency k with the minimum number of vertices consistent with this condition [12]. An embeddable g net of valency k corresponds to a graph of girth g which can be drawn on a surface in such a way that every face is bounded by a circuit of length g. Similarities between g nets and known g cages are investigated and a possible 5 cage of valency 6 is produced. An existence theorem for regular g nets is also given.     

Generation of Cubic Graphs and Snarks with Large Girth

We describe two new algorithms for the generation of all non‐isomorphic cubic graphs with girth at least that are very efficient for and show how these algorithms can be restricted to generate snarks with girth at least k. Our implementation of these algorithms is more than 30, respectively 40 times faster than the previously fastest generator for cubic graphs with girth at least six and seven, respectively. Using these generators we have also generated all nonisomorphic snarks with girth at least six up to 38 vertices and show that there are no snarks with girth at least seven up to 42 vertices. We present and analyze the new list of snarks with girth 6.