排序方式: 共有16条查询结果,搜索用时 859 毫秒
1.
Stephan Matos Camacho 《Discrete Mathematics》2009,309(15):4916-4919
In 1992 Gyárfás showed that a graph G having only k odd cycle lengths is (2k+1)-colourable, if it does not contain a K2k+2. In this paper, we will present the results for graphs containing only odd cycles of length 2m−1 and 2m+1 as done in [S. Matos Camacho, Colourings of graph with prescribed cycle lengths, diploma thesis, TU Bergakademie Freiberg, 2006. [3]]. We will show that these graphs are 4-colourable. 相似文献
2.
Xuding Zhu 《Discrete Mathematics》1998,190(1-3):215-222
Suppose G is a graph. The chromatic Ramsey number rc(G) of G is the least integer m such that there exists a graph F of chromatic number m for which the following is true: for any 2-colouring of the edges of F there is a monochromatic subgraph isomorphic to G. Let Mn = min[rc(G): χ(G) = n]. It was conjectured by Burr et al. (1976) that Mn = (n − 1)2 + 1. This conjecture has been confirmed previously for n 4. In this paper, we shall prove that the conjecture is true for n = 5. We shall also improve the upper bounds for M6 and M7. 相似文献
3.
For a given set M of positive integers, a problem of Motzkin asks for determining the maximal density μ(M) among sets of nonnegative integers in which no two elements differ by an element of M. The problem is completely settled when |M|?2, and some partial results are known for several families of M for |M|?3, including the case where the elements of M are in arithmetic progression. We consider some cases when M either contains an arithmetic progression or is contained in an arithmetic progression. 相似文献
4.
P.E. Haxell 《Journal of Combinatorial Theory, Series A》2006,113(1):67-83
Let Cn denote the 3-uniform hypergraph loose cycle, that is the hypergraph with vertices v1,…,vn and edges v1v2v3, v3v4v5, v5v6v7,…,vn-1vnv1. We prove that every red-blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of Cn, where N is asymptotically equal to 5n/4. Moreover this result is (asymptotically) best possible. 相似文献
5.
6.
Xuding Zhu 《Discrete Mathematics》2009,309(18):5562-5568
Given a graph G and a positive integer p, χp(G) is the minimum number of colours needed to colour the vertices of G so that for any i≤p, any subgraph H of G of tree-depth i gets at least i colours. This paper proves an upper bound for χp(G) in terms of the k-colouring number of G for k=2p−2. Conversely, for each integer k, we also prove an upper bound for in terms of χk+2(G). As a consequence, for a class K of graphs, the following two statements are equivalent:
- (a)
- For every positive integer p, χp(G) is bounded by a constant for all G∈K.
- (b)
- For every positive integer k, is bounded by a constant for all G∈K.
- (c)
- For every positive integer q, ∇q(G) (the greatest reduced average density of G with rank q) is bounded by a constant for all G∈K.
7.
The Grundy number of a graph G, denoted by Γ(G), is the largest k such that G has a greedyk-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this paper, we study the Grundy number of the lexicographic and cartesian products of two graphs in terms of the Grundy numbers of these graphs.Regarding the lexicographic product, we show that Γ(G)×Γ(H)≤Γ(G[H])≤2Γ(G)−1(Γ(H)−1)+Γ(G). In addition, we show that if G is a tree or Γ(G)=Δ(G)+1, then Γ(G[H])=Γ(G)×Γ(H). We then deduce that for every fixed c≥1, given a graph G, it is CoNP-Complete to decide if Γ(G)≤c×χ(G) and it is CoNP-Complete to decide if Γ(G)≤c×ω(G).Regarding the cartesian product, we show that there is no upper bound of Γ(G□H) as a function of Γ(G) and Γ(H). Nevertheless, we prove that Γ(G□H)≤Δ(G)⋅2Γ(H)−1+Γ(H). 相似文献
8.
本文介绍了TiF6光学玻璃的制作。研究了这种玻璃内的K+或Na+离子与Ag+离子交换。使用双光束干涉法观测了干涉纹、并用电子探针扫描电镜测量了Ag+、K+和Na+离子的浓度分布,还着重研究了离子交换后的玻璃裂纹和着色问题。最后,对结果作了讨论。 相似文献
9.
We prove that for each finite core graph G, the class of all graphs admitting a homomorphism into G is a pseudo-amalgamation class, in the sense of Fraı̈ssé. This fact gives rise to a countably infinite universal pseudo-homogeneous graph which shares some of the properties of the infinite random graph. Our methods apply simultaneously to G-colourings in several classes of relational structures, such as the classes of directed graphs or hypergraphs. 相似文献
10.