子立方无爪图的单射边色数至多为6

设$G$是一个图. 图$G$的一个单射边染色是指图$G$的一个边染色, 使得距离为$2$的两条边或者在同一个三角形中的两条边染不同的颜色. 图$G$的单射边色数是指图$G$的任意单射边染色所需要的最少颜色数. 关于单射边色数有一个猜想: 任意一个子立方图的单射边色数都不超过$6$. 在本文中, 我们证明了这个猜想对子立方无爪图是成立的, 并且给出图例说明上界$6$是紧的. 同时, 我们的证明隐含了求解这类图不超过$6$种颜色的单射边染色方案的一个线性时间算法.     

Upper Bounds for the Automorphic Chromatic Index of a Graph

The automorphic H-chromatic index of a graph Γ is the minimum integer m for which Γ has a proper edge-coloring with m colors preserved by a given subgroup H of the full automorphism group of Γ. We determine upper bounds for this index in terms of the chromatic index of Γ for some abelian 2-groups H.     

The Cycle Switching Graph of the Steiner Triple Systems of Order 19 is Connected

Switching is a local transformation that when applied to a combinatorial object gives another object with the same parameters. It is here shown that the cycle switching graph of the 11 084 874 829 isomorphism classes of Steiner triple systems of order 19 as well as the cycle switching graph of the 1 348 410 350 618 155 344 199 680 000 labeled such designs are connected. In addition to giving an understanding of the multitude of Steiner triple systems—at least for order 19 but perhaps also generally—this work also presents an algorithm for testing connectedness of large implicit graphs and brings forward a benchmark instance for such algorithms.     

Length of Longest Cycles in a Graph Whose Relative Length is at Least Two

Let G be a graph. We denote p(G) and c(G) the order of a longest path and the order of a longest cycle of G, respectively. Let κ(G) be the connectivity of G, and let σ ₃(G) be the minimum degree sum of an independent set of three vertices in G. In this paper, we prove that if G is a 2-connected graph with p(G) ? c(G) ≥ 2, then either (i) c(G) ≥ σ ₃(G) ? 3 or (ii) κ(G)?=?2 and p(G) ≥ σ ₃(G) ? 1. This result implies several known results as corollaries and gives a new lower bound of the circumference.     

The Sigma Chromatic Number of a Graph

For a nontrivial connected graph G, let ${c: V(G)\to {{\mathbb N}}}For a nontrivial connected graph G, let c: V(G)? \mathbb N{c: V(G)\to {{\mathbb N}}} be a vertex coloring of G, where adjacent vertices may be colored the same. For a vertex v of G, let N(v) denote the set of vertices adjacent to v. The color sum σ(v) of v is the sum of the colors of the vertices in N(v). If σ(u) ≠ σ(v) for every two adjacent vertices u and v of G, then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of a graph G is called its sigma chromatic number σ(G). The sigma chromatic number of a graph G never exceeds its chromatic number χ(G) and for every pair a, b of positive integers with a ≤ b, there exists a connected graph G with σ(G) = a and χ(G) = b. There is a connected graph G of order n with σ(G) = k for every pair k, n of positive integers with k ≤n if and only if k ≠ n − 1. Several other results concerning sigma chromatic numbers are presented.     

List Colouring When The Chromatic Number Is Close To the Order Of The Graph

Ohba has conjectured [7] that if G has 2 (G)+1 or fewer vertices then the list chromatic number and chromatic number of G are equal. In this short note we prove the weaker version of the conjecture obtained by replacing 2 (G)+1 by * This research was partially supported by DIMACS and by CNRS/NSF collaboration grant. Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey.     

图的色因子分解

设 ｎ１ ≥ ｎ ２ ≥ … ≥ ｎｋ ≥ ２ 是整数． 若图 Ｇ 能边分解成 Ｇ１  Ｇ２  …  Ｇｋ , 这里 χ（ Ｇｉ） ＝ ｎ ｉ, ｉ＝１,２,…,ｋ ,则称 Ｇ 有（ｎ１ , ｎ２ , …, ｎｋ ）色因子 分解． 本文改进 了 Ｈａｋｉｍ ｉ和 Ｓｃｈｍ ｅｉｃｈ ｅｌ 关于图的色因 子分解的结果,作为推 论,推广了 Ｍ ａｔｕｌａ 和 Ｈａｒａｒｙ 等人的结果     

无平方因子阶群的自同构群阶的上确界

群阶为素数方幂（即ｐ－ 群）时已得到该群自同构群阶的上确界,而对于其他情形的群,同样的问题要复杂得多． 本文在群阶无平方因子且为偶数时,给出了这类群的自同构群阶的上确界．     

Chromatic Index Critical Graphs of Even Order with Five Major Vertices

We prove that there does not exist any chromatic index critical graph of even order with exactly five vertices of maximum degree. This extends an earlier result of Chetwynd and Hilton who proved the same with five replaced by four or three.     

The Hamiltonian Index of a Graph

 It is proved that the hamiltonian index of a connected graph other than a path is less than its diameter which improves the results of P. A. Catlin etc. [J. Graph Theory 14 (1990) 347–364] and M. L. Sarazin [Discrete Math. 134(1994)85–91]. Nordhaus-Gaddum's inequalities for the hamiltonian index of a graph are also established. Received: July 17, 1998 Final version received: September 13, 1999     

Bounds to the Chromatic Polynomial of a Graph

In this paper, we present a simple inductive proof of some recently published bounds to the chromatic polynomial of a graph.     

The Index of a Periodic Graph

For periodic graphs, a special class of infinite, but locally finite graphs, an index theory is developed that can serve in classifying these graphs and that enables connections with various graph invariants as in the case of finite graphs. The index is defined with the aid of certain finite matrices that result rather canonically from reductions of the infinite adjacency operator due to the periodicity. As a central result we derive a sharp global lower bound for the index of any periodic graph.     

A Classification of Graphs Whose Subdivision Graph is Locally Distance Transitive

The subdivision graph S(Σ) of a connected graph Σ is constructed by adding a vertex in the middle of each edge. In a previous paper written with Cheryl E. Praeger, we characterised the graphs Σ such that S(Σ) is locally (G, s)-distance transitive for s ≤ 2 diam(Σ) ? 1 and some G?≤ Aut(Σ). In this paper, we solve the remaining cases by classifying all the graphs Σ such that S(Σ) is locally (G, s)-distance transitive for some s?≥ 2 diam(Σ) and some G?≤ Aut(Σ). As a corollary, we get a classification of all the graphs whose subdivision graph is locally distance transitive.     

On Connected Transversals to Subgroups Whose Order is a Product of Two Primes

We consider finite groups which have connected transversals to subgroups whose order is a product of two primespandq. We investigate those values ofpandqfor which the group is soluble. We can show that the solubility of the group follows ifq = 2 andp ≤ 61,q = 3 andp ≤ 31,q = 5 andp ≤ 11. We then apply our results on loop theory and we show that if the inner mapping group of a finite loop has orderpqwherepandqare as above then the loop is soluble.     

The Chromatic Index of Projective Triple Systems

We prove that, for even m, the chromatic index of the projective triple system STS( equals .     

关于重图的边色数

本文利用 A.Ehrenfeucht[2 ]等提出的两个引理 ,给出两个重图边色数的定理 .     

积空间是D -空间的空间类

人们知道每个C-似空间是 D -空间, 且每个正则弱θ -可加细 C-散布空间也是D -空间。上述空间类的积空间还是D -空间吗?在这篇文章中作者讨论了该问题, 得到如下结论：正则弱θ -可加细空间的有限积是D -空间; 正则Lindel\"of C-散布空间的可数积是D -空间     

Kneser图的分数染色临界性

图犌的一个分数染色是从犌的独立集的集合ζ 到区间［０，１］的一个映射犆，使得对任意顶点狓，都有： Σ 犛∈ζ，ｓ．ｔ．狓∈狊犆（犛）１，我们将此分数染色的值定义为Σ犛∈ζ犮（犛）．图犌的分数色数χ犳（犌）是它的所有分数染色的值的下确界．给出了分数染色临界性的定义并讨论了Ｋｎｅｓｅｒ图的分数染色临界性．