超图的强星色数

图的星色数的概念是由Ａ．Ｖｉｎｃｅ（１９８８）首次提出来的,它是图的色数的一个自然而又重要的推广,Ｌ．Ｈａｄａｄ等人（１９９４）将这一概念推广到一致超图,定义了ｈ－一致超图的强（弱）星色数,这里我们给出一般超图的强星色数的概念,研究了它的基本性质,计算了３－一致循环超图的强星色数,它们的强星色数形成了一个严格介于３和４之间的递减序列．     

D-完全一致混合超图不可着色的一个充要条件

混合超图的上,下色数与C-超边和D-超边数有着必然联系.一般地,增加C边会使下色数x(H)增加,增加D-超边会使上色数(x)(H)减小.本论文对D-完全一致混合超图进行研究,利用组合数学中分划思想及方法得到的D-完全一致混合超图不可着色的一个充要条件,对D-完全一致混合超图能否着色找到了可行的依据,进一步揭示C-超边数...     

反超图的笛卡儿积的上色数

讨论反超图的笛卡儿积的着色理论 ,求出了满足一定条件的反超图的笛卡儿积的上色数 .     

Oriented hypergraphs,stability numbers and chromatic numbers

Oriented hypergraphs are defined, so that it is possible to generalize propositions characterizing the chromatic number and the stability number of a graph by means of orientations and elementary paths, to the strong and weak chromatic number and the strong and weak stability number of a hypergraph.     

Hypergraphs with Zero Chromatic Threshold

Let F be an r-uniform hypergraph. The chromatic threshold of the family of F-free, r-uniform hypergraphs is the infimum of all non-negative reals c such that the subfamily of F-free, r-uniform hypergraphs H with minimum degree at least \(c \left( {\begin{array}{c}|V(H)|\\ r-1\end{array}}\right) \) has bounded chromatic number. The study of chromatic thresholds of various graphs has a long history, beginning with the early work of Erd?s and Simonovits. One interesting problem, first proposed by ?uczak and Thomassé and then solved by Allen, Böttcher, Griffiths, Kohayakawa and Morris, is the characterization of graphs having zero chromatic threshold, in particular the fact that there are graphs with non-zero Turán density that have zero chromatic threshold. Here, we make progress on this problem for r-uniform hypergraphs, showing that a large class of hypergraphs have zero chromatic threshold in addition to exhibiting a family of constructions showing another large class of hypergraphs have non-zero chromatic threshold. Our construction is based on a particular product of the Bollobás–Erd?s graphs defined earlier by the authors.     

Balanced matrices

This paper studies some properties of hypergraphs in connection with a class of integer linear programming problems. The main result (theorem 3) states that the strong chromatic number of a balanced hypergraph is equal to its rank; this generalizes a result known for unimodular hypergraphs. Two applications of this result are given, the first one to Graph theory (theorem 5), the second one to integral linear programming (theorem 6).     

Random hypergraph coloring algorithms and the weak chromatic number

We present a hypergraph coloring algorithm and analyze its performance in spaces of random hypergrpahs. In these spaces the number of colors used by our algorithm is almost surely within a small constant factor (less than 2) of the weak chromatic number of the hypergraph. This also establishes new upper and lower bounds for the weak chromatic number of uniform hypergraphs.     

Applications of hypergraph coloring to coloring graphs not inducing certain trees

We present a simple result on coloring hypergraphs and use it to obtain bounds on the chromatic number of graphs which do not induce certain trees.     

Dichotomy theorems for countably infinite dimensional analytic hypergraphs

We give classical proofs, strengthenings, and generalizations of Lecomte’s characterizations of analytic ω-dimensional hypergraphs with countable Borel chromatic number.     

Nombre chromatique total d'un hypergraphe

In this paper, the author defines a hypergraph total chromatic number and determines this number for the complete h-partite and for the complete h-uniform hypergraphs.     

About the upper chromatic number of a co-hypergraph

A mixed hypergraph consists of two families of subsets: the edges and the co-edges. In a coloring every co-edge has at least two vertices of the same color, and every edge has at least two vertices of different colors. The largest and smallest possible number of colors in a coloring is termed the upper and lower chromatic numbers, respectively. In this paper we investigate co-hypergraphs i.e., the hypergraphs with only co-edges, with respect to the property of coloring. The relationship between the lower bound of the size of co-edges and the lower bound of the upper chromatic number is explored. The necessary and sufficient conditions for determining the upper chromatic numbers, of a co-hypergraph are provided. And the bounds of the number of co-edges of some uniform co-hypergraphs with certain upper chromatic numbers are given.     

4一致(ξ)-超图的最小边数的上界

主要讨论了4一致l-超图的最小边数与最小上色数的关系,给出了上色数为3的4一致l-超图的最小边数的一个上界.     

4一致反超图的最小边数问题

混合超图是在超图的基础上添加一个反超边得到的图．超边和反超边的区别主要体现在着色要求上．在着色中,要求每一超边至少要有两个点着不同的颜色,而每一反超边至少有两个点着相同的颜色．最大最小颜色数分别称为混合超图的上色数和下色数。本文主要研究反超图,即只含反超边的超图。讨论了上色数为3的4一致超图的最小边数问题．给出了上色数为3的4一致反超图的最小边数的一个上界和一个下界．     

Extremal problems,partition theorems,symmetric hypergraphs

We compare extremal theorems such as Turán’s theorem with their corresponding partition theorems such as Ramsey’s theorem. We derive a general inequality involving chromatic number and independence number of symmetric hypergraphs. We give applications to Ramsey numbers and to van der Waerden numbers.     

关于Mycielski图循环色数的猜想

通过引进Mycielski图点集的一类特殊划分,利用该划分在Mycielski图循环着色中的特点改进了如下猜想:完全图的Mycielski图的循环色数等于它的点色数.     

The circular chromatic numbers of planar digraphs

The circular chromatic number is a refinement of the chromatic number of a graph. It has been established in [3,6,7] that there exists planar graphs with circular chromatic number r if and only if r is a rational in the set {1} ∪ [2,4]. Recently, Mohar, in [1,2] has extended the concept of the circular chromatic number to digraphs and it is interesting to ask what the corresponding result is for digraphs. In this article, we shall prove the new result that there exist planar digraphs with circular chromatic number r if and only if r is a rational in the interval [1,4]. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 14–26, 2007     

Coloring graphs by translates in the circle

The fractional and circular chromatic numbers are the two most studied non-integral refinements of the chromatic number of a graph. Starting from the definition of a coloring base of a graph, which originated in work related to ergodic theory, we formalize the notion of a gyrocoloring of a graph: the vertices are colored by translates of a single Borel set in the circle group, and neighboring vertices receive disjoint translates. The corresponding gyrochromatic number of a graph always lies between the fractional chromatic number and the circular chromatic number. We investigate basic properties of gyrocolorings. In particular, we construct examples of graphs whose gyrochromatic number is strictly between the fractional chromatic number and the circular chromatic number. We also establish several equivalent definitions of the gyrochromatic number, including a version involving all finite abelian groups.     

Circular choosability is rational

The circular choosability or circular list chromatic number of a graph is a list-version of the circular chromatic number, that was introduced by Mohar in 2002 and has been studied by several groups of authors since then. One of the nice properties that the circular chromatic number enjoys is that it is a rational number for all finite graphs G, and a fundamental question, posed by Zhu and reiterated by others, is whether the same holds for the circular choosability. In this paper we show that this is indeed the case.     

推广的奇轮的圆色数

图G的圆色数(又称"星色数")xc(G)是Vince在1988年提出的,它是图的色数 的自然推广.本文由奇轮出发构造了一族平面图,并证明了此类图的圆色数恰恰介于2和 3之间,填补了该领域的空白.     

推广的Mycielski图和类推广的Mycielski图的(邻点可区别的)全染色

Mycielski图是在1955年由Mycielski首先提出的,推广的Mycielski图是在2003年由Peter Che Bor Lam,林文松等给出的Mycielski图的一个自然推广,且研究了它的圆色数.目前关于推广的Mycielski图性质以及它们在点色数,分数色数,圆色数等方面已有许多研究.本文定义了推广的Mycielski图的另一推广称为类推广的Mycielski图,且探讨了推广的Mycielski图和类推广的Mycielski图在全染色、邻点可区别全染色方面与原基础图的关系,从而也得到了它们满足全染色猜想和邻点可区别全染色猜想及它们达到全色数和邻点可区别的全色数的下界的一些充分条件.