List coloring of graphs having cycles of length divisible by a given number

Let G be a graph and χ_l(G) denote the list chromatic number of G. In this paper we prove that for every graph G for which the length of each cycle is divisible by l (l≥3), χ_l(G)≤3.     

Long paths and cycles in oriented graphs

We obtain several sufficient conditions on the degrees of an oriented graph for the existence of long paths and cycles. As corollaries of our results we deduce that a regular tournament contains an edge-disjoint Hamilton cycle and path, and that a regular bipartite tournament is hamiltonian.     

On short cycles in triangle-free oriented graphs

An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on n vertices with minimum outdegree d contains a directed cycle of length at most ?n/d?. In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that α0 is the smallest real such that every n-vertex digraph with minimum outdegree at least α₀n contains a directed triangle. Let ε < (3 ? 2α₀)/(4 ? 2α₀) be a positive real. We show that if D is an oriented graph without directed triangles and has minimum outdegree and minimum indegree at least (1/(4 ? 2α₀)+ε)|D|, then each vertex of D is contained in a directed cycle of length l for each 4 ≤ l < (4 ? 2α₀)ε|D|/(3 ? 2α₀) + 2.     

Longest paths and cycles in bipartite oriented graphs

In this paper we obtain two sufficient conditions, Ore type (Theorem 1) and Dirac type (Theorem 2), on the degrees of a bipartite oriented graph for ensuring the existence of long paths and cycles. These conditions are shown to be the best possible in a sense.     

Nonseparable graphs with a given number of cycles

G. Ringel conjectured that for every positive integer n other than 2, 4, 5, 8, 9, and 16, there exists a nonseparable graph with n cycles. It is proved here that the conjecture is true even with the restriction to planar and hamiltonian graphs.     

The structure of graphs with given lengths of cycles

The cycle spectrum of a given graph G is the lengths of cycles in G. In this paper, we introduce the following problem: determining the maximum number of edges of an n-vertex graph with given cycle spectrum. In particular, we determine the maximum number of edges of an n-vertex graph without containing cycles of lengths three and at least k. This can be viewed as an extension of a well-known result of Erd?s and Gallai concerning the maximum number of edges of an n-vertex graph without containing cycles of lengths at least k. We also determine the maximum number of edges of an n-vertex graph whose cycle spectrum is a subset of two positive integers.     

Berge graphs with chordless cycles of bounded length

A graph is called weakly triangulated if it contains no chordless cycle on five or more vertices (also called hole) and no complement of such a cycle (also called antihole). Equivalently, we can define weakly triangulated graphs as antihole-free graphs whose induced cycles are isomorphic either to C₃ or to C₄. The perfection of weakly triangulated graphs was proved by Hayward [Hayward, J Combin Theory B. 39 (1985), 200–208] and generated intense studies to efficiently solve, for these graphs, the classical NP-complete problems that become polynomial on perfect graphs. If we replace, in the definition above, the C₄ by an arbitrary C_p (p even, at least equal to 6), we obtain new classes of graphs whose perfection is shown in this article. In fact, we prove a more general result: for any even integer p ≥ 6, the graphs whose cycles are isomorphic either to C₃ or to one of C_p, C_p+2, …, C_{2p 6} are perfect. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 73–79, 1999     

On the oriented chromatic number of graphs with given excess

The excess of a graph G is defined as the minimum number of edges that must be deleted from G in order to get a forest. We prove that every graph with excess at most k has chromatic number at most and that this bound is tight. Moreover, we prove that the oriented chromatic number of any graph with excess k is at most k+3, except for graphs having excess 1 and containing a directed cycle on 5 vertices which have oriented chromatic number 5. This bound is tight for k?4.     

Longest cycles in k-connected graphs with given independence number

The Chvátal–Erd?s Theorem states that every graph whose connectivity is at least its independence number has a spanning cycle. In 1976, Fouquet and Jolivet conjectured an extension: If G is an n-vertex k-connected graph with independence number a, and a?k, then G has a cycle with length at least . We prove this conjecture.     

Factorizations of product graphs into cycles of uniform length

The following question is raised by Alspach, Bermond and Sotteau: IfG ₁ has a decomposition into hamilton cycles and a 1-factor, andG ₂ has a hamilton cycle decmposition (HCD), does their wreath productG ₁ *G ₂ admit a hamilton cycle decomposition? In this paper the above question is answered with an additional condition onG ₁. Further it is shown that some product graphs can be decomposed into cycles of uniform length, that is, the edge sets of the graphs can be partitioned into cycles of lengthk, for some suitablek.     

Four‐cycles in graphs without a given even cycle

We prove that every bipartite C_2l‐free graph G contains a C₄‐free subgraph H with e(H) ≥ e(G)/(l – 1). The factor 1/(l – 1) is best possible. This implies that ex(n, C_2l) ≤ 2(l – 1)ex(n, {C₄, C_2l}), which settles a special case of a conjecture of Erd?s and Simonovits. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 147–156, 2005     

不含偶圈双圈图的极小斜能量

令G为简单连通图. 给图G的每条边赋予一个方向, 得到的有向图, 记为G^\sigma. 有向图G^\sigma的斜能量E_{s}(G^{\sigma})定义为G^\sigma的斜邻接矩阵特征值的绝对值之和. 令\mathcal{B}^\circ_{n}表示顶点个数为n不含偶圈的双圈图的集合. 考虑了\mathcal{B}^\circ_{n}中图依斜能量从小到大的排序问题. 利用有向图斜能量的积分公式和实分析的方法, 当n \geq 156和155 \geq n\geq 12时, 分别得到了\mathcal{B}^\circ_{n}中具有最小、次二小和次三小斜能量的双圈图.     

Embedding graphs in Cayley graphs

IfY is a finite graph then it is known that every sufficiently large groupG has a Cayley graph containing an induced subgraph isomorphic toY. This raises the question as to what is sufficiently large. Babai and Sós have used a probabilistic argument to show that |G| > 9.5 |Y|³ suffices. Using a form of greedy algorithm we strengthen this to (2 + \sqrt 3 )|Y|^3 $$ " align="middle" border="0"> . Some related results on finite and infinite groups are included.     

An exact minimum degree condition for Hamilton cycles in oriented graphs

We show that every sufficiently large oriented graph G with⁺(G), ^–(G)(3n–4)/8 contains a Hamilton cycle. Thisis best possible and solves a problem of Thomassen from 1979.     

Small cycles and 2-factor passing through any given vertices in graphs

The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G, let σ ₂(G):=min?{d(u)+d(v)|uv ? E(G),u≠v}. In the paper, the main results of this paper are as follows:

1. Let k≥2 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k of length at most four such that v _i ∈V(C _i ) for all 1≤i≤k.
2. Let k≥1 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k such that:
   1. v _i ∈V(C _i ) for all 1≤i≤k.
   2. V(C ₁)∪???∪V(C _k )=V(G), and
   3. |C _i |≤4, 1≤i≤k?1.

Moreover, the condition on σ ₂(G)≥n+2k?2 is sharp.     

Relative length of longest paths and longest cycles in triangle-free graphs

In this paper, we study triangle-free graphs. Let G=(V,E) be an arbitrary triangle-free graph with minimum degree at least two and σ₄(G)?|V(G)|+2. We first show that either for any path P in G there exists a cycle C such that |V_P?V_C|?1, or G is isomorphic to exactly one exception. Using this result, we show that for any set S of at most δ vertices in G there is a cycle C such that S⊆V_C.