共查询到20条相似文献，搜索用时 15 毫秒
1.
In 1960, Dirac posed the conjecture that r‐connected 4‐critical graphs exist for every r ≥ 3. In 1989, Erd?s conjectured that for every r ≥ 3 there exist r‐regular 4‐critical graphs. In this paper, a technique of constructing r‐regular r‐connected vertex‐transitive 4‐critical graphs for even r ≥ 4 is presented. Such graphs are found for r = 6, 8, 10. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 103–130, 2004 相似文献
2.
3.
J. Díaz A. C. Kaporis G. D. Kemkes L. M. Kirousis X. Pérez N. Wormald 《Journal of Graph Theory》2009,61(3):157-191
It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is asymptotically almost surely equal to 3, provided a certain four‐variable function has a unique maximum at a given point in a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the number of locally rainbow balanced 3‐colorings, where a coloring is balanced if the number of vertices of each color is equal, and locally rainbow if every vertex is adjacent to at least one vertex of each of the other colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 157–191, 2009 相似文献
4.
A.V. Pyatkin 《Journal of Graph Theory》2001,37(4):243-246
This note contains an example of a 4‐chromatic graph which admits a vertex partition into three parts such that the union of every two of them induces a forest. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 243–246, 2001 相似文献
5.
设Hn(n≥5)表示一个图:以1,2,．．．,n为顶点,两个点i和j是相邻的当且仅当|i-j|≤2,其中加法取模n．这篇文章证明了,Hn的色数等于它的选择数．结果被用于刻画最大度至多2的图的列表全色数． 相似文献
6.
冯纪先 《数学的实践与认识》2005,35(1):106-111
对简单完整正则平面图的特性和结构进行了分析和讨论 ,找出了简单完整正则平面图的可能的种类 .此外 ,对各种简单完整正则平面图的色数进行了求解 ,并用不同的方法给出了各个简单完整正则平面图的作色方案 . 相似文献
7.
Mycielski图的循环色数 总被引：1，自引：0，他引：1
通过引入一类点集划分的概念,研究了Mylielski图循环染色的性质,证明了当完全图的点数足够大时,它的Mycielski图的循环色数与其点色数相等. 相似文献
8.
9.
Atsuhiro Nakamoto 《Journal of Graph Theory》1999,30(3):223-234
In this article, we show that all quadrangulations of the sphere with minimum degree at least 3 can be constructed from the pseudo‐double wheels, preserving the minimum degree at least 3, by a sequence of two kinds of transformations called “vertex‐splitting” and “4‐cycle addition.” We also consider such generating theorems for other closed surfaces. These theorems can be translated into those of 4‐regular graphs on surfaces by taking duals. © 1999 John Wiley & Sons, In. J Graph Theory 30: 223–234, 1999 相似文献
10.
Given a bipartite graph H and a positive integer n such that v(H) divides 2n, we define the minimum degree threshold for bipartite H‐tiling, δ2(n, H), as the smallest integer k such that every bipartite graph G with n vertices in each partition and minimum degree δ(G)≥k contains a spanning subgraph consisting of vertex‐disjoint copies of H. Zhao, Hladký‐Schacht, Czygrinow‐DeBiasio determined δ2(n, Ks, t) exactly for all s?t and suffi‐ciently large n. In this article we determine δ2(n, H), up to an additive constant, for all bipartite H and sufficiently large n. Additionally, we give a corresponding minimum degree threshold to guarantee that G has an H‐tiling missing only a constant number of vertices. Our δ2(n, H) depends on either the chromatic number χ(H) or the critical chromatic number χcr(H), while the threshold for the almost perfect tiling only depends on χcr(H). These results can be viewed as bipartite analogs to the results of Kuhn and Osthus [Combinatorica 29 (2009), 65–107] and of Shokoufandeh and Zhao [Rand Struc Alg 23 (2003), 180–205]. © 2011 Wiley Periodicals, Inc. J Graph Theory 相似文献
11.
Let D be a set of positive integers. The distance graph G(Z,D) with distance set D is the graph with vertex set Z in which two vertices x,y are adjacent if and only if |x−y|D. The fractional chromatic number, the chromatic number, and the circular chromatic number of G(Z,D) for various D have been extensively studied recently. In this paper, we investigate the fractional chromatic number, the chromatic number, and the circular chromatic number of the distance graphs with the distance sets of the form Dm,[k,k′]={1,2,…,m}−{k,k+1,…,k′}, where m, k, and k′ are natural numbers with m≥k′≥k. In particular, we completely determine the chromatic number of G(Z,Dm,[2,k′]) for arbitrary m, and k′. 相似文献
12.
赋权图的区间染色的定义与赋权图的圆染色的定义非常类型,唯一的区别就是将Ｇ的顶点对应圆周上的孤换为Ｇ的顶点对应区间上的子区间,讨论了赋权的圆染色与区染色的关系。 相似文献
13.
This note proves that the game chromatic number of an outerplanar graph is at most 7. This improves the previous known upper bound of the game chromatic number of outerplanar graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 67–70, 1999 相似文献
14.
We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001 相似文献
15.
16.
We show a connection between two concepts that have hitherto been investigated separately, namely convex‐round graphs and circular cliques. The connections are twofold. We prove that the circular cliques are precisely the cores of convex‐round graphs; this implies that convex‐round graphs are circular‐perfect, a concept introduced recently by Zhu [10]. Secondly, we characterize maximal Kr‐free convex‐round graphs and show that they can be obtained from certain circular cliques in a simple fashion. Our proofs rely on several structural properties of convex‐round graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 182–194, 2002 相似文献
17.
18.
Given positive integers m, k, and s with m > ks, let Dm,k,s represent the set {1, 2, …, m} − {k, 2k, …, sk}. The distance graph G(Z, Dm,k,s) has as vertex set all integers Z and edges connecting i and j whenever |i − j| ∈ Dm,k,s. The chromatic number and the fractional chromatic number of G(Z, Dm,k,s) are denoted by χ(Z, Dm,k,s) and χf(Z, Dm,k,s), respectively. For s = 1, χ(Z, Dm,k,1) was studied by Eggleton, Erdős, and Skilton [6], Kemnitz and Kolberg [12], and Liu [13], and was solved lately by Chang, Liu, and Zhu [2] who also determined χf(Z, Dm,k,1) for any m and k. This article extends the study of χ(Z, Dm,k,s) and χf(Z, Dm,k,s) to general values of s. We prove χf(Z, Dm,k,s) = χ(Z, Dm,k,s) = k if m < (s + 1)k; and χf(Z, Dm,k,s) = (m + sk + 1)/(s + 1) otherwise. The latter result provides a good lower bound for χ(Z, Dm,k,s). A general upper bound for χ(Z, Dm,k,s) is obtained. We prove the upper bound can be improved to ⌈(m + sk + 1)/(s + 1)⌉ + 1 for some values of m, k, and s. In particular, when s + 1 is prime, χ(Z, Dm,k,s) is either ⌈(m + sk + 1)/(s + 1)⌉ or ⌈(m + sk + 1)/(s + 1)⌉ + 1. By using a special coloring method called the precoloring method, many distance graphs G(Z, Dm,k,s) are classified into these two possible values of χ(Z, Dm,k,s). Moreover, complete solutions of χ(Z, Dm,k,s) for several families are determined including the case s = 1 (solved in [2]), the case s = 2, the case (k, s + 1) = 1, and the case that k is a power of a prime. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 245–259, 1999 相似文献
19.
图的倍图与补倍图 总被引：7，自引：0，他引：7
计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题．对简单图C,如果V（D（G））：V（G）∪V（G′）E（D（G））=E（C）∪E（C″）U{vivj′｜vi∈V（G）,Vj′∈V（G′）且vivj∈E（G））那么,称D（C）是C的倍图,如果V（D（G））=V（C）∪V（G′）,E（D（C））：E（C）∪E（G′）∪{vivj′}vi∈V（G）,vj′∈V（G’）and vivj∈（G））,称D（C）是G的补倍图,这里G′是G的拷贝．本文研究了D（G）和D的色数,边色数,欧拉性,哈密顿性和提出了D（G） 的边色数是D（G）的最大度等公开问题． 相似文献
20.
On the complete chromatic number of Halin graphs 总被引：8，自引：0，他引：8
ThisresearchissupportedbytheNationalNaturalScienceFoundationofChina.Write.1.IntroductionDefinition1.FOrany3-connectedplanargraphG(V,E,F)withA(G)23,iftheboundaryedgesoffacefowhichisadjacenttotheothersareremoved,itbecomesatree,andthedegreeofeachvertexofV(fo)is3,andthenGiscalledaHalingraph;foiscalledtheouterfaceofG,andtheotherscalledtheinteriorfaces,thevenicesonthefacefoarecalledtheoutervenices,theoillersarecalledtheinterior...ti..,tll.ForanyplanargraphG(V,E,F),f,f'eF,fisadjacenttof'ifan… 相似文献