On 3-choosable planar graphs of girth at least 4

Let G be a plane graph of girth at least 4. Two cycles of G are intersecting if they have at least one vertex in common. In this paper, we show that if a plane graph G has neither intersecting 4-cycles nor a 5-cycle intersecting with any 4-cycle, then G is 3-choosable, which extends one of Thomassen’s results [C. Thomassen, 3-list-coloring planar graphs of girth 5, J. Combin. Theory Ser. B 64 (1995) 101-107].     

Do 3n − 5 edges force a subdivision of K5?

A conjecture of Dirac states that every simple graph with n vertices and 3n ? 5 edges must contain a subdivision of K₅. We prove that a topologically minimal counterexample is 5-connected, and that no minor-minimal counterexample contains K₄ – e. Consequently, Dirac's conjecture holds for all graphs that can be embedded in a surface with Euler characteristic at least ? 2.     

Almost all graphs with 1.44n edges are 3-colorable

We establish a uniform asymptotic approximation of certain probabilities arising in the coupon collector's problem. Then we use this approximation to prove that almost all graphs with n vertices and 1.44 n edges contain no subgraph with minimum degree at least three, and hence are 3-colorable.     

On circle graphs with girth at least five

Circle graphs with girth at least five are known to be 2-degenerate [A.A. Ageev, Every circle graph with girth at least 5 is 3-colourable, Discrete Math. 195 (1999) 229-233]. In this paper, we prove that circle graphs with girth at least g≥5 and minimum degree at least two contain a chain of g−4 vertices of degree two, which implies Ageev’s result in the case g=5. We then use this structural property to give an upper bound on the circular chromatic number of circle graphs with girth at least g≥5 as well as a precise estimate of their maximum average degree.     

On 3-regular graphs having crossing number at least 2

We give a planar proof of the fact that if G is a 3-regular graph minimal with respect to having crossing number at least 2, then the crossing number of G is 2.     

On 3-connected minors of 3-connected matroids and graphs

Whittle proved, for k=1,2, that if N is a 3-connected minor of a 3-connected matroid M, satisfying r(M)−r(N)≥k, then there is a k-independent set I of M such that, for every x∈I, si(M/x) is a 3-connected matroid with an N-minor. In this paper, we establish this result for k=3. It is already known that it cannot be extended to greater values of k. But, here we also show that, in the graphic case, with the extra assumption that r(M)−r(N)≥6, we can guarantee the existence of a 4-independent set of M with such a property. Moreover, in the binary case, we show that if r(M)−r(N)≥5, then M has such a 4-independent set or M has a triangle T meeting 3 triads and such that M/T is a 3-connected matroid with an N-minor.     

On graphs with cut vertices and cut edges

Let G（n,k,t） be a set of graphs with n vertices,k cut edges and t cut vertices.In this paper,we classify these graphs in G（n,k,t） according to cut vertices,and characterize the extremal graphs with the largest spectral radius in G（n,k,t）.     

On σ-equivalence and χ-equivalence of graphs

We define a partial ordering on the set of σ-polynomials as well as a vertex splitting operation on the set of graphs, and introduce the notions of σ-equivalence and σ-uniqueness of graphs. Let σ(G) be the σ-polynomial of a graph G and (OVERBAR)σ(G) = σ(G^c). Let H = (G, v, A, B) be a vertex splitting graph of G. We prove that (OVERBAR)σ(G) ≤ (OVERBAR)σ(H) and the equality holds if and only if every vertex of A is adjacent to every vertex of B. This gives us an effective means to find σ-equivalent and χ-equivalent graphs. A necessary and sufficient condition for a graph to be χ-unique but not σ-unique is also obtained. © 1996 John Wiley & Sons, Inc.     

Clique‐inverse graphs of K3‐free and K4‐free graphs

The clique graph K(G) of a given graph G is the intersection graph of the collection of maximal cliques of G. Given a family ℱ of graphs, the clique‐inverse graphs of ℱ are the graphs whose clique graphs belong to ℱ. In this work, we describe characterizations for clique‐inverse graphs of K₃‐free and K₄‐free graphs. The characterizations are formulated in terms of forbidden induced subgraphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 257–272, 2000     

Labelled graphs with vertices of degree at least three

The generating function for labelled graphs in which each vertex has degree at least three is obtained by the Principle of Inclusion and Exclusion. Asymptotic and explicit values for the coefficients are calculated in the connected case. The results are extended to bipartite graphs.     

Altitude of regular graphs with girth at least five

The altitude of a graph G is the largest integer k such that for each linear ordering f of its edges, G has a (simple) path P of length k for which f increases along the edge sequence of P. We determine a necessary and sufficient condition for cubic graphs with girth at least five to have altitude three and show that for r?4, r-regular graphs with girth at least five have altitude at least four. Using this result we show that some snarks, including all but one of the Blanus?a type snarks, have altitude three while others, including the flower snarks, have altitude four. We construct an infinite class of 4-regular graphs with altitude four.     

Contractible edges inn-connected graphs with minimum degree greater than or equal to [5n/4]

It is proved that ifG is ann-connected graph with minimum degree greater than or equal to [5n/4],n 4, thenG has an edgee such that the graph obtained fromG by contractinge is stilln-connected.Dedicated to Professor Nagayoshi Iwahori on his 60th birthday     

The edge reconstruction hypothesis is true for graphs with more than n · log2n edges

It is shown that a graph with n vertices and more than n · log₂n edges can be uniquely reconstructed from its edge-deleted subgraphs.     

On graphs having σ-polynomials of the same degree

Frucht and Giudici classified all graphs having quadratic σ-polynomials. Dhurandhar characterized all graphs having quadratic and cubic σ-polynomials. Here, we give a necessary and sufficient condition for the graphs whose σ-polynomials are of degree k where k is any positive integer. By using this condition, we construct all graphs whose σ-polynomials are of degree 2, 3 and 4. For the quadratic and cubic cases, our results are the same as those of Frucht, Giudici and Dhurandhar's.