共查询到20条相似文献,搜索用时 91 毫秒
1.
2.
M.Kriesell证明了收缩临界5-连通图的平均度不超过24并猜想收缩临界5-连通图的平均度小于10.本文构造了一个反例证明M.Kriesell的猜想不成立并给出了收缩临界5-连通图平均度新的上界. 相似文献
3.
三类笛卡尔积图的关联色数 总被引:2,自引:0,他引:2
图的关联色数的概念是 Brualdi和 Massey于 1 993年引入的 ,它同图的强色指数有密切的关系 .Guiduli[2 ] 说明关联色数是有向星萌度的一个特殊情况 ,迄今仅确定了某些特殊图类的关联色数 .本文给出了完全图与完全图、圈与完全图、圈与圈的笛卡尔积图的关联色数。 相似文献
4.
5.
《数学的实践与认识》2013,(23)
利用圈矩阵和图论的相关知识,研究一类双色有向图,它的未着色图中包含n+m-4个顶点,一个n-圈和一个m-圈,给出了本原条件和指数上界,并对达到指数上界的极图进行了刻画. 相似文献
6.
树T中γL=γt的若干充分条件 总被引:1,自引:0,他引:1
全九γt和小控制数γL是图的两个重要的控制参数。本文探讨并给出了在树中γL与γt相等的一些充分条件。同时,利用中介点组理顺了树中不同点集之间的关系,为证明关于γL与γt比值的上界不超过3/2的猜想提供了一个重要思路。 相似文献
7.
讨论n阶正对角元本原矩阵A的r级组合合成Cr(A),得到了它的本原指数的上界:r(Cr(A))≤n-r,r=1,2,…,n,解决了文[4]中的一个猜想.进而得出,设Mr={Cr(A)|A是n阶正对角元本原矩阵},Mr中所有合成阵的本原指数集填满{1,2,…,n-r}. 相似文献
8.
关于图的符号边全控制数 总被引:1,自引:0,他引:1
引入了图的符号边全控制的概念,给出了一个连通图G的符号边全控制数γs′t(G)的下限,确定所有n阶树T的最小符号边全控制数,并刻划了满足γs′t(G)=E(G)的所有连通图G,最后还提出了一个关于γs′t(G)上界的猜想. 相似文献
9.
10.
本文给出方程n=3时分别正好存在1个闭解,3个闭解,以及至少存在2个闭解的充分条件,并研究了这些闭解的稳定性.当n=4且ai(t)(i=0,1,2,3)为t的P次多项式时,文[1]曾猜想其时闭解重数的上界为max{4,p+3}.本文举例指出,即使p=3,闭解重数的上界也可以大于7.这说明该猜想不成立 相似文献
11.
We consider a distance generalisation of the strong chromatic index and the maximum induced matching number. We study graphs of bounded maximum degree and Erd?s–Rényi random graphs. We work in three settings. The first is that of a distance generalisation of an Erd?s–Ne?et?il problem. The second is that of an upper bound on the size of a largest distance matching in a random graph. The third is that of an upper bound on the distance chromatic index for sparse random graphs. One of our results gives a counterexample to a conjecture of Skupień. 相似文献
12.
13.
Most upper bounds for the chromatic index of a graph come from algorithms that produce edge colorings. One such algorithm was invented by Vizing [Diskret Analiz 3 (1964), 25–30] in 1964. Vizing's algorithm colors the edges of a graph one at a time and never uses more than Δ+µ colors, where Δ is the maximum degree and µ is the maximum multiplicity, respectively. In general, though, this upper bound of Δ+µ is rather generous. In this paper, we define a new parameter fan(G) in terms of the degrees and the multiplicities of G. We call fan(G) the fan number of G. First we show that the fan number can be computed by a polynomial‐time algorithm. Then we prove that the parameter Fan(G)=max{Δ(G), fan(G)} is an upper bound for the chromatic index that can be realized by Vizing's coloring algorithm. Many of the known upper bounds for the chromatic index are also upper bounds for the fan number. Furthermore, we discuss the following question. What is the best (efficiently realizable) upper bound for the chromatic index in terms of Δ and µ ? Goldberg's Conjecture supports the conjecture that χ′+1 is the best efficiently realizable upper bound for χ′ at all provided that P ≠ NP . © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 115–138, 2010 相似文献
14.
In 1976, Stahl [14] defined the m-tuple coloring of a graph G and formulated a conjecture on the multichromatic number of Kneser graphs. For m=1 this conjecture is Kneser’s conjecture, which was proved by Lovász in 1978 [10]. Here we show that Lovász’s topological lower bound given in this way cannot be used to prove Stahl’s conjecture. We obtain that the strongest index bound only gives the trivial m⋅ω(G) lower bound if m≥|V(G)|. On the other hand, the connectivity bound for Kneser graphs is constant if m is sufficiently large. These findings provide new examples of graphs showing that the gaps between the chromatic number, the index bound and the connectivity bound can be arbitrarily large. 相似文献
15.
对|V(G)|≥3的连通图G,若κ-正常边染色法满足相邻点的色集合不相同,则称该染色法为κ-邻强边染色,其最小的κ称为图G的邻强边色数。张忠辅等学者猜想:对|V(G)|≥3的连通图G,G≠C_5其邻强边色数至多为△(G)+2,利用组合分析的方法给出了完全图的广义Mycielski图的邻强边色数,从而验证了图的邻强边染色猜想对于此类图成立。 相似文献
16.
The clique number of an undirected graph G is the maximum order of a complete subgraph of G and is a well‐known lower bound for the chromatic number of G. Every proper k‐coloring of G may be viewed as a homomorphism (an edge‐preserving vertex mapping) of G to the complete graph of order k. By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this article, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray conjectured that the order of a planar oriented clique is at most 15, which was later proved by Sen. We show that any planar oriented clique on 15 vertices must contain a particular oriented graph as a spanning subgraph, thus reproving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth k for all . 相似文献
17.
Maximum Genus of Strong Embeddings 总被引:4,自引:0,他引:4
Er-lingWei Yan-peiLiu HanRen 《应用数学学报(英文版)》2003,19(3):437-446
The strong embedding conjecture states that any 2-connected graph has a strong embedding on some surface. It implies the circuit double cover conjecture: Any 2-connected graph has a circuit double cover.Conversely, it is not true. But for a 3-regular graph, the two conjectures are equivalent. In this paper, a characterization of graphs having a strong embedding with exactly 3 faces, which is the strong embedding of maximum genus, is given. In addition, some graphs with the property are provided. More generally, an upper bound of the maximum genus of strong embeddings of a graph is presented too. Lastly, it is shown that the interpolation theorem is true to planar Halin graph. 相似文献
18.
19.
主要讨论了4一致l-超图的最小边数与最小上色数的关系,给出了上色数为3的4一致l-超图的最小边数的一个上界. 相似文献
20.
《Discrete Mathematics》2020,343(10):112021
In this note we show every orientation of a connected cubic graph admits an oriented 8-colouring. This lowers the best-known upper bound for the chromatic number of the family of orientations of connected cubic graphs. We further show that every such oriented graph admits a 2-dipath 7-colouring. These results imply that either the oriented chromatic number for the family of orientations of connected cubic graphs equals the 2-dipath chromatic number or the long-standing conjecture of Sopena (Sopena, 1997) regarding the chromatic number of orientations of connected cubic graphs is false. 相似文献