3一致完全超图的彩色哈密顿圈

假设c是一个小于1/1152的常数,证明：对于每个充分大的偶数n,如果一个具有n个顶点的3一致完全超图的边着色满足每种颜色出现的次数不超过[cn],那么必含有一个每条边颜色都不一样的彩色哈密顿圈。     

本原简单超图的指数集

设H是一个超图, 用H\+*和L(H)分别表示H的对偶超图和线图. 定义H的邻接图是由L(H\+*)和H的所有环组成的图, 记作G\-H. 若G\-H是本原的, 则称H是本原的, 并称γ(G\-H)为H的指数. 该文得到了所有n阶本原简单超图以及所有秩不小于3的n阶本原简单超图的指数集, 并分别刻划了其极超图.     

几类图的匹配等价图类

两个图G和H的匹配多项式相等,则称它们匹配等价.用[G]表示图G的所有不同构的匹配等价图的集合.刻画了匹配次大根小于1的图及这些图的补图的匹配等价图类.     

I形图的匹配等价图类

完全刻画了In以及它的补图的匹配等价图类。     

最大匹配图的围长

将一个图的所有最大匹配作为顶点集,称两个最大匹配相邻,若它们之一通过交换一条边得到另一个,由引所得图为该图的最大匹配图。本文研究了最大匹配图的围长,从而给出了最大匹配图是树或完全图的条件。     

两类图的匹配等价类

完全刻画了Ｐｍ和Ｋ１∪Ｇｍ以及它们的补图的匹配等价图类。     

秩为r的本原超图的指数集(英文)

本文研究了超图的本原性质.运用图论方法,得到了具有秩r(≥3)的所有n阶本原有向超图的指数集,并刻划了其极超图.     

一类Caterpillars图的匹配刻画

利用匹配多项式的性质以及匹配根的信息研究了图的匹配刻画问题,给出了一类Caterpillars图F（2,m,3）及补图匹配刻画的充分必要条件是m=2,5,8.     

关于Lovasz不等式的几类超图

本文证明了下面的定理：若超图Ｈ＝（Ｘ；Ｅ１，Ｅ２，．．．Ｅｍ）中存在浓度为Ｋ长为ｍ的圈，则有ｍ∑ｉ＝１（│Ｅｉ│－ｋ）＞ｎ－ｋ。     

几类图的匹配唯一性

若图G的匹配多项式为M(G;W),对任何图H,M(G;W)=M(H;W)推出G与H同构,则称G是匹配唯一的.本文讨论了下面的几种图类:(i)B_(m,n,r);(ii)D_(m,n,r);(iii)T_(m,n)的匹配唯一性问题,从而得到一些较为满意的结果.     

A note on rainbow matchings in strongly edge-colored graphs

The Ryser Conjecture which states that there is a transversal of size $n$ in a Latin square of odd order $n$ is equivalent to finding a rainbow matching of size $n$ in a properly edge-colored $K_{n,n}$ using $n$ colors when $n$ is odd. Let $\delta$ be the minimum degree of a graph. Wang proposed a more general question to find a function $f\left(\delta \right)$ such that every properly edge-colored graph of order $f\left(\delta \right)$ contains a rainbow matching of size $\delta$, which currently has the best bound of $f\left(\delta \right)\le 3.5\delta +2$ by Lo. Babu, Chandran and Vaidyanathan investigated Wang’s question under a stronger color condition. A strongly edge-colored graph is a properly edge-colored graph in which every monochromatic subgraph is an induced matching. Wang, Yan and Yu proved that every strongly edge-colored graph of order at least $2\delta +2$ has a rainbow matching of size $\delta$. In this note, we extend this result to graphs of order at least $2\delta +1$.     

Packing perfect matchings in random hypergraphs

We introduce a new procedure for generating the binomial random graph/hypergraph models, referred to as online sprinkling. As an illustrative application of this method, we show that for any fixed integer , the binomial ‐uniform random hypergraph contains edge‐disjoint perfect matchings, provided , where is an integer depending only on . Our result for is asymptotically optimal and for is optimal up to the factor. This significantly improves a result of Frieze and Krivelevich.     

Existence of rainbow matchings in properly edge-colored graphs

Let G be a properly edge-colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let δ denote the minimum degree of G. We show that if |V(G)| > (δ ² + 14δ + 1)/4, then G has a rainbow matching of size δ, which answers a question asked by G. Wang [Electron. J. Combin., 2011, 18: #N162] affirmatively. In addition, we prove that if G is a properly colored bipartite graph with bipartition (X, Y) and max{|X|, |Y|} > (δ ² + 4δ − 4)/4, then G has a rainbow matching of size δ.     

Disjoint perfect matchings in 3‐uniform hypergraphs

For a hypergraph H, let denote the minimum vertex degree in H. Kühn, Osthus, and Treglown proved that, for any sufficiently large integer n with , if H is a 3‐uniform hypergraph with order n and then H has a perfect matching, and this bound on is best possible. In this article, we show that under the same conditions, H contains at least pairwise disjoint perfect matchings, and this bound is sharp.     

Rainbow matchings in Dirac bipartite graphs

We show the existence of rainbow perfect matchings in μn‐bounded edge colorings of Dirac bipartite graphs, for a sufficiently small μ > 0. As an application of our results, we obtain several results on the existence of rainbow k‐factors in Dirac graphs and rainbow spanning subgraphs of bounded maximum degree on graphs with large minimum degree.     

On perfect matchings in matching covered graphs

A graph is matching-covered if every edge of is contained in a perfect matching. A matching-covered graph is strongly coverable if, for any edge of , the subgraph is still matching-covered. An edge subset of a matching-covered graph is feasible if there exist two perfect matchings and such that , and an edge subset with at least two edges is an equivalent set if a perfect matching of contains either all edges in or none of them. A strongly matchable graph does not have an equivalent set, and any two independent edges of form a feasible set. In this paper, we show that for every integer , there exist infinitely many -regular graphs of class 1 with an arbitrarily large equivalent set that is not switching-equivalent to either or , which provides a negative answer to a problem of Lukot’ka and Rollová. For a matching-covered bipartite graph , we show that has an equivalent set if and only if it has a 2-edge-cut that separates into two balanced subgraphs, and is strongly coverable if and only if every edge-cut separating into two balanced subgraphs and satisfies and .     

The rainbow number of matchings in regular bipartite graphs

Given a graph G and a subgraph H of G, let rb(G,H) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H. The number rb(G,H) is called the rainbow number of H with respect to G. Denote as mK₂ a matching of size m and as B_n,k the set of all the k-regular bipartite graphs with bipartition (X,Y) such that X=Y=n and k≤n. Let k,m,n be given positive integers, where k≥3, m≥2 and n>3(m−1). We show that for every GB_n,k, rb(G,mK₂)=k(m−2)+2. We also determine the rainbow numbers of matchings in paths and cycles.     

Rainbow number of matchings in planar graphs

The rainbow number$rb(G,H)$ for the graph $H$ in $G$ is defined to be the minimum integer $c$ such that any $c$-edge-coloring of $G$ contains a rainbow $H$. As one of the most important structures in graphs, the rainbow number of matchings has drawn much attention and has been extensively studied. Jendrol et al. initiated the rainbow number of matchings in planar graphs and they obtained bounds for the rainbow number of the matching $k{K}_2$ in the plane triangulations, where the gap between the lower and upper bounds is $O\left(k^3\right)$. In this paper, we show that the rainbow number of the matching $k{K}_2$ in maximal outerplanar graphs of order $n$ is $n+O\left(k\right)$. Using this technique, we show that the rainbow number of the matching $k{K}_2$ in some subfamilies of plane triangulations of order $n$ is $2n+O\left(k\right)$. The gaps between our lower and upper bounds are only $O\left(k\right)$.     

Edge intersection graphs of linear 3-uniform hypergraphs

Let be the class of edge intersection graphs of linear 3-uniform hypergraphs. It is known that the problem of recognition of the class is NP-complete. We prove that this problem is polynomially solvable in the class of graphs with minimum vertex degree ≥10. It is also proved that the class is characterized by a finite list of forbidden induced subgraphs in the class of graphs with minimum vertex degree ≥16.     

Exponentially many perfect matchings in cubic graphs

We show that every cubic bridgeless graph G has at least ²|V(G)|/3656 perfect matchings. This confirms an old conjecture of Lovász and Plummer.