Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

Contractible Triples in Highly Connected Graphs

We prove that if G is k-connected (with k ≥ 2), then G contains either a cycle of length 4 or a connected subgraph of order 3 whose contraction results in a k-connected graph. This immediately implies that any k-connected graph has either a cycle of length 4 or a connected subgraph of order 3 whose deletion results in a (k − 1)-connected graph.     

Spanning Trees with Few Leaves

In this paper, we prove that an m-connected graph G on n vertices has a spanning tree with at most k leaves (for k ≥ 2 and m ≥ 1) if every independent set of G with cardinality m + k contains at least one pair of vertices with degree sum at least n − k + 1. This is a common generalization of results due to Broersma and Tuinstra and to Win.     

Graphs G for which both G and G¯ are Contraction Critically k-Connected

 An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is called contraction critically k-connected. For k≥4, we prove that if both G and its complement Gˉ are contraction critically k-connected, then |V(G)|<k ^5/3+4k ^3/2. Received: October, 2001 Final version received: September 18, 2002 AMS Classification: 05C40     

A Local Property of Large Polyhedral Maps on Compact 2-Dimensional Manifolds

We prove that each polyhedral map G on a compact 2-manifold, which has large enough vertices, contains a k-path, a path on k vertices, such that each vertex of it has, in G, degree at most 6k; this bound being best possible for k even. Moreover, if G has large enough vertices of degree >6k, than it contains a k-path such that each its vertex has degree, in G, at most 5k; this bound is best possible for any k. Received: December 8, 1997 Revised: April 27, 1998     

Spanning k-Trees of n-Connected Graphs

A tree is called a k-tree if the maximum degree is at most k. We prove the following theorem, by which a closure concept for spanning k-trees of n-connected graphs can be defined. Let k ≥ 2 and n ≥ 1 be integers, and let u and v be a pair of nonadjacent vertices of an n-connected graph G such that deg _G (u) + deg _G (v) ≥ |G| − 1 − (k − 2)n, where |G| denotes the order of G. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree.     

Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any , let , and , and and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.      

A note on a spanning 3-tree

A tree T is called a k-tree, if the maximum degree of T is at most k. In this paper, we prove that if G is an n-connected graph with independence number at most n + m + 1 (n≥1,n≥m≥0), then G has a spanning 3-tree T with at most m vertices of degree 3.     

Subgraphs with Restricted Degrees of Their Vertices in Planar 3-Connected Graphs

We have proved that every 3-connected planar graph G either contains a path on k vertices each of which has degree at most 5k or does not contain any path on k vertices; the bound 5k is the best possible. Moreover, for every connected planar graph H other than a path and for every integer m ≥ 3 there is a 3-connected planar graph G such that each copy of H in G contains a vertex of degree at least m.     

Longest Cycles in Almost Claw-Free Graphs

Some known results on claw-free graphs are generalized to the larger class of almost claw-free graphs. In this paper, we prove several properties on longest cycles in almost claw-free graphs. In particular, we show the following two results.? (1) Every 2-connected almost claw-free graph on n vertices contains a cycle of length at least min {n, 2δ+4} and the bound 2δ+ 4 is best possible, thereby fully generalizing a result of Matthews and Sumner.? (2) Every 3-connected almost claw-free graph on n vertices contains a cycle of length at least min {n, 4δ}, thereby fully generalizing a result of MingChu Li. Received: September 17, 1996 Revised: September 22, 1998     

On the Convexity Number of Graphs

A set of vertices S in a graph is convex if it contains all vertices which belong to shortest paths between vertices in S. The convexity number c(G) of a graph G is the maximum cardinality of a convex set of vertices which does not contain all vertices of G. We prove NP-completeness of the problem to decide for a given bipartite graph G and an integer k whether c(G) ≥ k. Furthermore, we identify natural necessary extension properties of graphs of small convexity number and study the interplay between these properties and upper bounds on the convexity number.     

Distance-Dominating Cycles in Quasi Claw-Free Graphs

We say that a graph G is quasi claw-free if every pair (a ₁, a ₂) of vertices at distance 2 satisfies {u∈N (a ₁)∩N (a ₂) | N[u]⊆N[a ₁]∪N [a ₂]}≠∅. A cycle C is m-dominating if every vertex of G is of distance at most m from C. We prove that if G is a κ-connected (κ≥2) quasi claw-free graph then either G has an m-dominating cycle or G has a set of at least κ+1 vertices such that the distance between every pair of them is at least 2m+3. Received: June 12, 1996 Revised: November 9, 1998     

The Entire Coloring of Series-Parallel Graphs

The entire chromatic number X_(vef)(G) of a plane graph G is the minimal number of colors needed for coloring vertices, edges and faces of G such that no two adjacent or incident elements are of the same color. Let G be a series-parallel plane graph, that is, a plane graph which contains no subgraphs homeomorphic to K_(4-) It is proved in this paper that X_(vef)(G)≤max{8, △(G) 2} and X_(vef)(G)=△ 1 if G is 2-connected and △(G)≥6.     

On the Circumference of 3-Connected Quasi-Claw-Free Graphs

A graph G is quasi-claw-free if it satisfies the property: d(x,y)=2 ⇒ there exists such that . In the paper, we prove that the circumference of a 3-connected quasi-claw-free graph G on n vertices is at least min{4δ−2,n} and G is hamiltonian if n≤5δ−5.     

Minimally Non-Preperfect Graphs of Small Maximum Degree

 A graph G is called preperfect if each induced subgraph G ^′⊆G of order at least 2 has two vertices x, y such that either all maximum cliques of G ^′ containing x contain y, or all maximum independent sets of G ^′ containing y contain x, too. Giving a partial answer to a problem of Hammer and Maffray [Combinatorica 13 (1993), 199–208], we describe new classes of minimally non-preperfect graphs, and prove the following characterizations: (i) A graph of maximum degree 4 is minimally non-preperfect if and only if it is an odd cycle of length at least 5, or the complement of a cycle of length 7, or the line graph of a 3-regular 3-connected bipartite graph. (ii) If a graph G is not an odd cycle and has no isolated vertices, then its line graph is minimally non-preperfect if and only if G is bipartite, 3-edge-connected, regular of degree d for some d≥3, and contains no 3-edge-connected d ^′-regular subgraph for any 3≤d ^′<d. Received: March 4, 1998 Final version received: August 14, 1999     

Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs

Given a function f : ℕ→ℝ, call an n-vertex graph f-connected if separating off k vertices requires the deletion of at least f(k) vertices whenever k≤(n−f(k))/2. This is a common generalization of vertex connectivity (when f is constant) and expansion (when f is linear). We show that an f-connected graph contains a cycle of length linear in n if f is any linear function, contains a 1-factor and a 2-factor if f(k)≥2k+1, and contains a Hamilton cycle if f(k)≥2(k+1)². We conjecture that linear growth of f suffices to imply hamiltonicity.     

Sparse Graphs which Decompose into Closed Trails of Arbitrary Lengths

A simple, connected even graph G with vertex set V(G) and edge set E(G) is said to be ADCT (Arbitrarily Decomposable into Closed Trails) if for any collection of positive integers x ₁, x ₂,...,x _m with and x _i ≥ 3 for 1 ≤ i ≤ m, there exists a decomposition of G into closed trails (circuits) of lengths x ₁, x ₂,...,x _m . In this note we construct an 8-regular ADCT graph on 6n vertices, for each each n ≥ 3. On the other hand, we also show that there are only finitely many 4-regular graphs which are ADCT. Received July 26, 2006. Final version received: March 5, 2008.     

Longest Cycles in 3-connected Graphs with Given Independence Number

Fouquet and Jolivet conjectured that a k-connected graph of order n and independence number α ≥ k has a cycle of length at least [Fouquet and Jolivet, Problèmes combinatoires et théorie des graphes Orsay (1976), Problems, page 438]. Here we prove this conjecture for k=3.     

Total Colorings Of Degenerate Graphs

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. A graph G is s-degenerate for a positive integer s if G can be reduced to a trivial graph by successive removal of vertices with degree ≤s. We prove that an s-degenerate graph G has a total coloring with Δ+1 colors if the maximum degree Δ of G is sufficiently large, say Δ≥4s+3. Our proof yields an efficient algorithm to find such a total coloring. We also give a lineartime algorithm to find a total coloring of a graph G with the minimum number of colors if G is a partial k-tree, that is, the tree-width of G is bounded by a fixed integer k.     

Removable edges in cycles of a <Emphasis Type="Italic">k</Emphasis>-connected graph

An edge e of a k-connected graph G is said to be a removable edge if G ⊖ e is still k-connected, where G ⊖ e denotes the graph obtained from G by deleting e to get G − e, and for any end vertex of e with degree k − 1 in G − e, say x, delete x, and then add edges between any pair of non-adjacent vertices in N _G−e (x). The existence of removable edges of k-connected graphs and some properties of 3-connected graphs and 4-connected graphs have been investigated. In the present paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph (k ≥ 4).