Unit Interval Graphs of Open and Closed Intervals

We give two structural characterizations of the class of finite intersection graphs of the open and closed real intervals of unit length. This class is a proper superclass of the well‐known unit interval graphs.     

3‐Coloring Triangle‐Free Planar Graphs with a Precolored 8‐Cycle

Let G be a planar triangle‐free graph and let C be a cycle in G of length at most 8. We characterize all situations where a 3‐coloring of C does not extend to a proper 3‐coloring of the whole graph.     

一类几乎唯一泛圈图

设G是阶为n的简单Hamilton图．若存在m(3(?)m相似文献   

Finding large cycles in Hamiltonian graphs

We show how to find in Hamiltonian graphs a cycle of length n^{Ω(1/loglogn)}=exp(Ω(logn/loglogn)). This is a consequence of a more general result in which we show that if G has a maximum degree d and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in O(n³) time a cycle in G of length k^Ω(1/logd). From this we infer that if G has a cycle of length k, then one can find in O(n³) time a cycle of length k^{Ω(1/(log(n/k)+loglogn))}, which implies the result for Hamiltonian graphs. Our results improve, for some values of k and d, a recent result of Gabow (2004) [11] showing that if G has a cycle of length k, then one can find in polynomial time a cycle in G of length . We finally show that if G has fixed Euler genus g and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in polynomial time a cycle in G of length f(g)k^Ω(1), running in time O(n²) for planar graphs.     

Balanced Cayley graphs and balanced planar graphs

A balanced graph is a bipartite graph with no induced circuit of length . These graphs arise in integer linear programming. We focus on graph-algebraic properties of balanced graphs to prove a complete classification of balanced Cayley graphs on abelian groups. Moreover, in this paper, we prove that there is no cubic balanced planar graph. Finally, some remarkable conjectures for balanced regular graphs are also presented. The graphs in this paper are simple.     

2-连通半无爪图的最长圈

A graph G is called quasi-claw-free if it satisfies the property:d(x,y)=2 there exists a vertex u∈N(x)∩N(y)such that N[u]■N[x]∪N[y].In this paper,we show that every 2-connected quasi-claw-free graph of order n with G■F contains a cycle of length at least min{3δ+2,n},where F is a family of graphs.     

The existence of even factors in iterated line graphs

An even factor of a graph is a spanning subgraph of G in which all degrees are even, positive integers. In this paper, we characterize the claw-free graphs having even factors and then prove that the n-iterated line graph Lⁿ(G) of G has an even factor if and only if every end branch of G has length at most n and every odd branch-bond of G has a branch of length at most n+1.     

完备图分拆为带一条弦的(2k-1)-长圈

本文给出了构造G-设计的一个统一方法及当v≡1(mod 4k)时的C_(2k-1)~((r))-GD(v)的存在性,其中C_(10)~((r)),1≤r≤k-2表示带一条弦的2k-1长圈,r表示弦两个端点间的顶点个数。     

Hamiltonian connected hourglass free line graphs

Thomassen [Reflections on graph theory, J. Graph Theory 10 (1986) 309-324] conjectured that every 4-connected line graph is hamiltonian. An hourglass is a graph isomorphic to K₅-E(C₄), where C₄ is a cycle of length 4 in K₅. In Broersma et al. [On factors of 4-connected claw-free graphs, J. Graph Theory 37 (2001) 125-136], it is shown that every 4-connected line graph without an induced subgraph isomorphic to the hourglass is hamiltonian connected. In this note, we prove that every 3-connected, essentially 4-connected hourglass free line graph, is hamiltonian connected.     

一类Kn-同胚图色等价类的结构特征

用K（s，n）表示完全图Kn的一条边被长为s（s≥2）的路Ps＋1替代后得到的图．对n≥7，且n-2为素数，刻画了色等价类【K（s，n）]中图的结构特征，进一步，证明了任意任意n≥7，且n-2为素数，K（2，n），K（3，n）是色唯一的．     

Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable

It is known that planar graphs without cycles of length from 4 to 7 are 3-colorable (Borodin et al., 2005) [13] and that planar graphs in which no triangles have common edges with cycles of length from 4 to 9 are 3-colorable (Borodin et al., 2006) [11]. We give a common extension of these results by proving that every planar graph in which no triangles have common edges with k-cycles, where k∈{4,5,7} (or, which is equivalent, with cycles of length 3, 5 and 7), is 3-colorable.     

Cycle decompositions III: Complete graphs and fixed length cycles

We show that the necessary conditions for the decomposition of the complete graph of odd order into cycles of a fixed even length and for the decomposition of the complete graph of even order minus a 1‐factor into cycles of a fixed odd length are also sufficient. © 2002 John Wiley & Sons, Inc. J Combin Designs 10: 27–78, 2002     

Regular path decompositions of odd regular graphs

Kotzig asked in 1979 what are necessary and sufficient conditions for a d‐regular simple graph to admit a decomposition into paths of length d for odd d>3. For cubic graphs, the existence of a 1‐factor is both necessary and sufficient. Even more, each 1‐factor is extendable to a decomposition of the graph into paths of length 3 where the middle edges of the paths coincide with the 1‐factor. We conjecture that existence of a 1‐factor is indeed a sufficient condition for Kotzig's problem. For general odd regular graphs, most 1‐factors appear to be extendable and we show that for the family of simple 5‐regular graphs with no cycles of length 4, all 1‐factors are extendable. However, for d>3 we found infinite families of d‐regular simple graphs with non‐extendable 1‐factors. Few authors have studied the decompositions of general regular graphs. We present examples and open problems; in particular, we conjecture that in planar 5‐regular graphs all 1‐factors are extendable. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 114–128, 2010     

Large cycles in random generalized Johnson graphs

This paper studies thresholds in random generalized Johnson graphs for containing large cycles, i.e. cycles of variable length growing with the size of the graph. Thresholds are obtained for different growth rates.     

On the fastest moving off from a vertex in directed regular graphs

Let Γ be a directed regular locally finite graph, and let $\bar \Gamma $ be the undirected graph obtained by forgetting the orientation of Γ. Let x be a vertex of Γ and let n be a nonnegative integer. We study the length of the shortest directed path in Γ starting at x and ending outside of the ball of radius n centered at x in $\bar \Gamma $ .     

3-连通3-正则图中的可序子集

图G的k元点集X={x1,x2,…,xk}被称为G的k-可序子集,如果X的任意排列都按序排在G的某个圈上.称G是k-可序图,如果G的每一个k元子集都是G的k-可序子集.称G为k-可序Hamilton图,如果X的任意排列都位于G的Hamilton圈上.研究了3-连通3-正则图的可序子集的存在性问题.     

Products of unit distance graphs

Some graphs admit drawings in the Euclidean plane (k-space) in such a (natural) way, that edges are represented as line segments of unit length. We say that they have the unit distance property.The influence of graph operations on the unit distance property is discussed. It is proved that the Cartesian product preserves the unit distance property in the Euclidean plane, while graph union, join, tensor product, strong product, lexicographic product and corona do not. It is proved that the Cartesian product preserves the unit distance property also in higher dimensions.     

最大匹配的路变换图

图G的最大匹配的路变换图NM(G)是这样一个图,它以G的最大匹配为顶点,如果两个最大匹配M_1与M_2的对称差导出的图是一条路(长度没有限制),那么M_1和M_2在NM(G)中相邻.研究了这个变换图的连通性,分别得到了这个变换图是一个完全图或一棵树或一个圈的充要条件.     

Planar graph colorings without short monochromatic cycles

It is well known that every planar graph G is 2‐colorable in such a way that no 3‐cycle of G is monochromatic. In this paper, we prove that G has a 2‐coloring such that no cycle of length 3 or 4 is monochromatic. The complete graph K₅ does not admit such a coloring. On the other hand, we extend the result to K₅‐minor‐free graphs. There are planar graphs with the property that each of their 2‐colorings has a monochromatic cycle of length 3, 4, or 5. In this sense, our result is best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 25–38, 2004     

Every signed planar graph without cycles of length from 4 to 8 is 3-colorable

In this paper, we investigate the signed graph version of Erdös problem: Is there a constant $c$ such that every signed planar graph without $k$-cycles, where $4\le k\le c$, is 3-colorable and prove that each signed planar graph without cycles of length from 4 to 8 is 3-colorable.