共查询到20条相似文献,搜索用时 78 毫秒
1.
2.
郑国彪 《纯粹数学与应用数学》2011,27(3):308-312
混合超图的上,下色数与C-超边和D-超边数有着必然联系.一般地,增加C边会使下色数x(H)增加,增加D-超边会使上色数(x)(H)减小.本论文对D-完全一致混合超图进行研究,利用组合数学中分划思想及方法得到的D-完全一致混合超图不可着色的一个充要条件,对D-完全一致混合超图能否着色找到了可行的依据,进一步揭示C-超边数... 相似文献
3.
带有不完全椭球约束的线性模型中线性估计的可容许性 总被引:17,自引:0,他引:17
本文刻划了线性模型(Y,Xβ,σ2V,V≥0)在不完全椭球约束:(β-β0)’N(β- β P0)≤σ2,N ≥ 0下的线性估计的可容许性.本文的结果显示了一个有趣的现象,即一个线性估计在全体线性估计所组成的类中的可容许性与椭球的中心β0无关,而在全体齐次线性估计所组成的类中的可容许性与β0有关. 相似文献
4.
图的路色数问题的NP-完全性 总被引:3,自引:0,他引:3
一个给定的图是否存在用r种颜色的正常Pk着色?称该问题为图的(k,r)路色数问题.本文研究其算法复杂性,并得到以下结果:对于任意给定的k,2≤k≤∞,图的(k,2)路色数问题及直径为2的图的(k,3)路色数问题都是NP-完全的;对于任意给定的k,2≤k≤∞,平面图的(k,3)路色数问题也是NP-完全的. 相似文献
5.
6.
一个给定的图是否存在用r种颜色的正常Pk着色?称该问题为图的(k,r)路色数问题。已知对于直径为2的图及任意给定的整数r≥3,图的(2,r)路色数问题是NP-完全的。本文给出直径为2的(2,2)路色图的一个好的刻划,并由此给出该问题的一个多项式时间算法,从而解决了以r为参数的直径为2的图的(2,r)路色数问题的计算复杂性分类。 相似文献
7.
对于一般的G-M模型Y-N(Xβ,σ^2V),V≥0,当Sβ不是线性可估的时,本文分别得到了矩阵损失下(Sβ,σ^2)的联合估计(LY+a.YAY)的估计类中和在一切估计的类中可容许的充要条件,以及在二次损失LY+a-Sβ+(YAY-σ^2)^2下和估计类中可容许的充要条件。 相似文献
8.
9.
关于虚二次域类数的可除性 总被引:2,自引:0,他引:2
设α>1,b>1,(α,b)=1,h(-αb)表虚二次域的类数。如果有正整数x,y,n,k满足(1)αx ̄2+by ̄2=4k ̄n,b且;或(2)αx ̄2+by ̄2=k ̄n,x|α,y|b且αb≡2(mod4),则本文证明了关于h(-αb)的可除性的两个定理(见定理1,2),其中符号x|α表示x的每一个素因子整除α。 相似文献
10.
如果一个图的顶点集可以划分为基数尽可能相等的k个独立集,则称该图是可均匀k-着色的.本文得到树可均匀k-着色的一些条件;直径为4的树可均匀k-着色的一个充分必要条件和均匀色数表达式. 相似文献
11.
Benjamin Doerr 《Discrete Applied Mathematics》2006,154(4):650-659
We propose an advanced randomized coloring algorithm for the problem of balanced colorings of hypergraphs (discrepancy problem). Instead of independently coloring the vertices with a random color, we try to use structural information about the hypergraph in the design of the random experiment by imposing suitable dependencies. This yields colorings having smaller discrepancy. We also obtain more information about the coloring, or, conversely, we may enforce the random coloring to have special properties. There are some algorithmic advantages as well.We apply our approach to hypergraphs of d-dimensional boxes and to finite geometries. Among others results, we gain a factor 2d/2 decrease in the discrepancy of the boxes, and reduce the number of random bits needed to generate good colorings for the geometries down to (from n). The latter also speeds up the corresponding derandomization by a factor of . 相似文献
12.
The notion of a split coloring of a complete graph was introduced by Erd?s and Gyárfás [ 7 ] as a generalization of split graphs. In this work, we offer an alternate interpretation by comparing such a coloring to the classical Ramsey coloring problem via a two‐round game played against an adversary. We show that the techniques used and bounds obtained on the extremal (r,m)‐split coloring problem of [ 7 ] are closer in nature to the Turán theory of graphs rather than Ramsey theory. We extend the notion of these colorings to hypergraphs and provide bounds and some exact results. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 226–237, 2002 相似文献
13.
D. de Werra 《Journal of Graph Theory》1979,3(2):175-182
Existence of some generalized edge colorings is proved by using the properties of hypergraphs as well as alternating chain methods. A general framework is given for edge colorings and some general properties of balancing are derived. 相似文献
14.
In this survey the following types of colorings of plane graphs are discussed, both in their vertex and edge versions: facially proper coloring, rainbow coloring, antirainbow coloring, loose coloring, polychromatic coloring, -facial coloring, nonrepetitive coloring, odd coloring, unique-maximum coloring, WORM coloring, ranking coloring and packing coloring.In the last section of this paper we show that using the language of words these different types of colorings can be formulated in a more general unified setting. 相似文献
15.
We consider proper online colorings of hypergraphs defined by geometric regions. We prove that there is an online coloring algorithm that colors N intervals of the real line using \({\Theta }(\log N/k)\) colors such that for every point p, contained in at least k intervals, not all the intervals containing p have the same color. We also prove the corresponding result about online coloring a family of wedges (quadrants) in the plane that are the translates of a given fixed wedge. These results contrast the results of the first and third author showing that in the quasi-online setting 12 colors are enough to color wedges (independent of N and k). We also consider quasi-online coloring of intervals. In all cases we present efficient coloring algorithms. 相似文献
16.
We investigate the relationship between two kinds of vertex colorings of graphs: unique-maximum colorings and conflict-free colorings. In a unique-maximum coloring, the colors are ordered, and in every path of the graph the maximum color appears only once. In a conflict-free coloring, in every path of the graph there is a color that appears only once. We also study computational complexity aspects of conflict-free colorings and prove a completeness result. Finally, we improve lower bounds for those chromatic numbers of the grid graph. 相似文献
17.
D. de Werra 《Discrete Mathematics》1979,27(3):309-316
A general framework for coloring problems is described; the concept of regular coloring is introduced; it simply means that one specifies in each edge the maximum and the minimum number of nodes which may have the same color.For several types of regular colorings, one defines canonical colorings where colors form an ordered set and where one always tries to use first the “smallest” colors. It is shown that for some classes of multigraphs including bipartite multigraphs, regular edge colorings corresponding to maximal color feasible sequences are canonical. 相似文献
18.
In this paper, we study the group and list group colorings of total graphs and present group coloring versions of the total and list total colorings conjectures. We establish the group coloring version of the total coloring conjecture for the following classes of graphs: graphs with small maximum degree, two-degenerate graphs, planner graphs with maximum degree at least 11, planner graphs without certain small cycles, outerplanar graphs and near outerplanar graphs with maximum degree at least 4. In addition, the group version of the list total coloring conjecture is established for forests, outerplanar graphs and graphs with maximum degree at most two. 相似文献
19.
Robert E. Jamison 《Discrete Applied Mathematics》2011,159(7):595-604
An edge coloring of a graph is orientable if and only if it is possible to orient the edges of the graph so that the color of each edge is determined by the head of its corresponding oriented arc. The goals of this paper include finding a forbidden substructure characterization of orientable colorings and giving a linear time recognition algorithm for orientable colorings.An edge coloring is lexical if and only if it is possible to number the vertices of the graph so that the color of each edge is determined by its lower endpoint. Lexical colorings are, of course, the orientable colorings in which the underlying orientation is acyclic. Lexical colorings play an important role in Canonical Ramsey theory, and it is this standpoint that motivates the current study. 相似文献
20.
Babson and Kozlov (2006) [2] studied Hom-complexes of graphs with a focus on graph colorings. In this paper, we generalize Hom-complexes to r-uniform hypergraphs (with multiplicities) and study them mainly in connection with hypergraph colorings. We reinterpret a result of Alon, Frankl and Lovász (1986) [1] by Hom-complexes and show a hierarchy of known lower bounds for the chromatic numbers of r-uniform hypergraphs (with multiplicities) using Hom-complexes. 相似文献