Contractible Non-Edges in Triangle-Free Graphs

Thomassen has proved that every triangle-free k-connected graph contains a pair of adjacent vertices whose identification yields again a k-connected graph. We study the existence of a pair of nonadjacent vertices whose identification preserves k-connectivity. In particular, we present a reduction theorem for the class of all bipartite, k-connected graphs. Revised: January 7, 1999     

The Generation of Maximal Triangle-Free Graphs

In this paper we present an efficient algorithm for generating maximal triangle-free graphs. A program based on this algorithm has been used to check a conjecture of Erdo´´s about the local density of triangle-free graphs and turned out to be very powerful for the computation of triangle Ramsey numbers.     

The Four-in-a-Tree Problem in Triangle-Free Graphs

The three-in-a-tree algorithm of Chudnovsky and Seymour decides in time O(n ⁴) whether three given vertices of a graph belong to an induced tree. Here, we study four-in- a-tree for triangle-free graphs. We give a structural answer to the following question: what does a triangle-free graph look like if no induced tree covers four given vertices? Our main result says that any such graph must have the “same structure”, in a sense to be defined precisely, as a square or a cube. We provide an O(nm)-time algorithm that given a triangle-free graph G together with four vertices outputs either an induced tree that contains them or a partition of V(G) certifying that no such tree exists. We prove that the problem of deciding whether there exists a tree T covering the four vertices such that at most one vertex of T has degree at least 3 is NP-complete.     

On The Structure Of Triangle-Free Graphs Of Large Minimum Degree

It is shown that for every ε>0 there exists a constant L such that every triangle-free graph on n vertices with minimum degree at least (1/3+ε)n is homomorphic to a triangle-free graph on at most L vertices. * Research partially supported by KBN grant 2 P03A 016 23.     

On the Chromatic Number of Triangle-Free Graphs of Large Minimum Degree

We prove that, for each xed real number c > 1/3, the triangle-free graphs of minimum degree at least cn (where n is the number of vertices) have bounded chromatic number. This problem was raised by Erds and Simonovits in 1973 who pointed out that there is no such result for c < 1/3.     

Oriented Coloring of Triangle-Free Planar Graphs and 2-Outerplanar Graphs

A graph is planar if it can be embedded on the plane without edge-crossings. A graph is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the external face is outerplanar (i.e. with all its vertices on the external face). An oriented k-coloring of an oriented graph G is a homomorphism from G to an oriented graph H of order k. We prove that every oriented triangle-free planar graph has an oriented chromatic number at most 40, that improves the previous known bound of 47 [Borodin, O. V. and Ivanova, A. O., An oriented colouring of planar graphs with girth at least 4, Sib. Electron. Math. Reports, vol. 2, 239–249, 2005]. We also prove that every oriented 2-outerplanar graph has an oriented chromatic number at most 40, that improves the previous known bound of 67 [Esperet, L. and Ochem, P. Oriented colouring of 2-outerplanar graphs, Inform. Process. Lett., vol. 101(5), 215–219, 2007].     

Large Induced Forests in Triangle-Free Planar Graphs

Given a planar graph G, what is the largest subset of vertices of G that induces a forest? Albertson and Berman [2] conjectured that every planar graph has an induced subgraph on at least half of the vertices that is a forest. For bipartite planar graphs, Akiyama and Wanatabe [1] conjectured that there is always an induced forest of size at least 5n/8. Here we prove that every triangle-free (and therefore every bipartite) planar graph on n vertices has an induced forest of size at least (17n+24)/32.     

The Size of Maximally Irregular Graphs and Maximally Irregular Triangle-Free Graphs

Let G be a graph. The irregularity index of G, denoted by t(G), is the number of distinct values in the degree sequence of G. For any graph G, t(G) ≤ Δ(G), where Δ(G) is the maximum degree. If t(G) = Δ(G), then G is called maximally irregular. In this paper, we give a tight upper bound on the size of maximally irregular graphs, and prove the conjecture proposed in [6] on the size of maximally irregular triangle-free graphs. Extremal graphs are also characterized.     

Triangle-Free Geometric Intersection Graphs with Large Chromatic Number

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set $X$ X in $\mathbb{R }^2$ R 2 that is not an axis-aligned rectangle and for any positive integer $k$ k produces a family $\mathcal{F }$ F of sets, each obtained by an independent horizontal and vertical scaling and translation of $X$ X , such that no three sets in $\mathcal{F }$ F pairwise intersect and $\chi (\mathcal{F })>k$ χ ( F ) > k . This provides a negative answer to a question of Gyárfás and Lehel for L-shapes. With extra conditions we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries or equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.     

秩$6$的无三角形的图

The rank of a graph G is defined to be the rank of its adjacency matrix A（G）. In this paper we characterize all connected triangle-free graphs with rank 6.     

不含三角形的图的λ3-最优性的充分条件

设G=(V,E)是一个连通图,边集S(?)E是一个3-限制性边割,如果G-S是不连通的并且G-S的每个分支至少有三个点.图G的3-限制性边连通度λ_3(G)是G中最小的一个3-限制性边割的基数.图G是λ_3(G)连通的,如果3-限制性边割存在.G是λ_3-最优的,如果λ_3(G)=ξ_3(G),其中ξ_3(G)=min{|[U,(?)]|:U(?)V,|U|=3 and G[U]是连通的).G[U]表示V的子集U的导出子图,(?)=V\U表示U的补.[U,(?)]是一条边的一个端点在U中另一个端点在(?)中的边的集合.本文给出了不含三角形的图是λ_3-最优的一些充分条件.     

A Note on Heterochromatic C 4 in Edge-Colored Triangle-Free Graphs

Let G be an edge-colored graph. A heterochromatic cycle of G is a cycle in which any pair of edges have distinct colors. Let d ^c (v), named the color degree of a vertex v, be defined as the maximum number of edges incident with v, that have distinct colors. In this paper, we prove that if G is an edge-colored triangle-free graph of order n ≥?9 and ${d^c(v) \geq \frac{(3-\sqrt{5})n}{2}+1}$ for each vertex v of G, G has a heterochromatic C ₄.     

Generating Random Regular Graphs

Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple algorithm introduced by Steger and Wormald [10] and prove that it produces an asymptotically uniform random regular graph in a polynomial time. Precisely, for fixed d and n with d = O(n^1/3−ε), it is shown that the algorithm generates an asymptotically uniform random d-regular graph on n vertices in time O(nd²). This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality by the second author. The algorithm works for relatively large d in practical (quadratic) time and can be used to derive many properties of uniform random regular graphs. * Research supported in part by grant RB091G-VU from UCSD, by NSF grant DMS-0200357 and by an A. Sloan fellowship.     

There are Finitely Many Triangle-Free Distance-Regular Graphs with Degree 8, 9 or 10

In this paper we prove that there are finitely many triangle-free distance-regular graphs with degree 8, 9 or 10.     

On Rationality of Generating Function for the Number of Spanning Trees in Circulant Graphs

Let F(x)=∑∞n=1 Tsi,s2,...,sk(n)x^n be the generating function for the number,Ts1bs2,...,sk(n) of spanning trees in the circulant graph Cn(s1,S2,...,Sk).We show that F(x)is a rational function with integer coefficients satisfying the property F(x)=F(l/x).A similar result is also true for the circulant graphs C2n(s1,S2,....,Sk,n)of odd valency.We illustrate the obtained results by a series of examples.     

门槛图与度极大图

证明了门槛图与度极大图是一类图的两种不同说法,同时用图的对角限制极左矩阵刻画这一类图的结构。     

LDPC Codes from Triangle-Free Line Sets

We study sets of lines of AG(n, q) and PG(n, q) with the property that no three lines form a triangle. As a result the associated point-line incidence graph contains no 6-cycles and necessarily has girth at least 8. One can then use the associated incidence matrices to form binary linear codes that can be considered as LDPC codes. The relatively high girth allows for efficient implementation of these codes. We give two general constructions for such triangle-free line sets and give the parameters for the associated codes when q is small.     

On Compact Graphs

Let G be a finite simple graph with adjacency matrix A, and let P（A） be the convex closure of the set of all permutation matrices commuting with A. G is said to be compact if every doubly stochastic matrix which commutes with A is in P（A）. In this paper, we characterize 3-regular compact graphs and prove that if G is a connected regular compact graph, G - v is also compact, and give a family of almost regular compact connected graphs.