共查询到20条相似文献,搜索用时 31 毫秒
1.
For a finite graphG letForb(H) denote the class of all finite graphs which do not containH as a (weak) subgraph. In this paper we characterize the class of those graphsH which have the property that almost all graphs inForb(H) are -colorable. We show that this class corresponds exactly to the class of graphs whose extremal graph is the Turán-graphT
n
().An earlier result of Simonovits (Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions,Discrete Math.
7 (1974), 349–376) shows that these are exactly the (+1)-chromatic graphs which contain a color-critical edge. 相似文献
2.
This paper introduces a new type of edge-coloring of multigraphs, called anfg-coloring, in which each color appears at each vertexv no more thanf(v) times and at each set of multiple edges joining verticesv andw no more thang(vw) times. The minimum number of colors needed tofg-color a multigraphG is called thefg-chromatic index ofG. Various upper bounds are given on thefg-chromatic index. One of them is a generalization of Vizing's bound for the ordinary chromatic index. Our proof is constructive, and immediately yields a polynomial-time algorithm tofg-color a given multigraph using colors no more than twice thefg-chromatic index. 相似文献
3.
Oleg Pikhurko 《Combinatorica》2008,28(2):187-208
Let Σ
k
consist of all k-graphs with three edges D
1, D
2, D
3 such that |D
1 ∩ D
2| = k − 1 and D
1 Δ D
2 ⊆ D
3. The exact value of the Turán function ex(n, Σ
k
) was computed for k = 3 by Bollobás [Discrete Math. 8 (1974), 21–24] and for k = 4 by Sidorenko [Math Notes 41 (1987), 247–259].
Let the k-graph T
k
∈ Σ
k
have edges
Frankl and Füredi [J. Combin. Theory Ser. (A) 52 (1989), 129–147] conjectured that there is n
0 = n
0(k) such that ex(n, T
k
) = ex(n, Σ
k
) for all n ≥ n
0 and had previously proved this for k = 3 in [Combinatorica 3 (1983), 341–349]. Here we settle the case k = 4 of the conjecture.
Reverts to public domain after 28 years from publication.
Partially supported by the National Science Foundation, Grant DMS-0457512. 相似文献
4.
In this paper we establish that decidingt-colorability for a simplek-graph whent≧3,k≧3 is NP-complete. Next, we establish that if there is a polynomial time algorithm for finding the chromatic number of a Steiner
Triple system then there exists a polynomial time “approximation” algorithm for the chromatic number of simple 3-graphs. Finally,
we show that the existence of such an approximation algorithm would imply that P=NP.
Dedicated to Paul Erdős on his seventieth birthday 相似文献
5.
In 1943, Hadwiger made the conjecture that every k-chromatic graph has a K
k
-minor. This conjecture is, perhaps, the most interesting conjecture of all graph theory. It is well known that the case k=5 is equivalent to the Four Colour Theorem, as proved by Wagner [39] in 1937. About 60 years later, Robertson, Seymour and Thomas [29] proved that the case k=6 is also equivalent to the Four Colour Theorem. So far, the cases k7 are still open and we have little hope to verify even the case k=7 up to now. In fact, there are only a few theorems concerning 7-chromatic graphs, e. g. [17].In this paper, we prove the deep result stated in the title, without using the Four Colour Theorem [1,2,28]. This result verifies the first unsettled case m=6 of the (m,1)-Minor Conjecture which is a weaker form of Hadwigers Conjecture and a special case of a more general conjecture of Chartrand et al. [8] in 1971 and Woodall [42] in 1990.The proof is somewhat long and uses earlier deep results and methods of Jørgensen [20], Mader [23], and Robertson, Seymour and Thomas [29].* Research partly supported by the Japan Society for the Promotion of Science for Young Scientists. Research partly supported by the Danish Natural Science Research Council.Dedicated to Professor Mike Plummer on the occasion of his sixty-fifth birthday. 相似文献
6.
Michael Stiebitz 《Combinatorica》1982,2(3):315-323
Tibor Gallai made the following conjecture. LetG be ak-chromatic colour-critical graph. LetL denote the set of those vertices ofG having valencyk−1 and letH be the rest ofV(G). Then the number of components induced byL is not less than the number of components induced byH, providedL ≠ 0.
We prove this conjecture in a slightly generalized form.
Dedicated to Tibor Gallai on his seventieth birthday 相似文献
7.
In “The structure of hereditary properties and colourings of random graphs” [Combinatorica
20(2) (2000), 173–202], Bollobás and the second author studied the probability of a hereditary property P in the probability space G(n,p). They found simple properties that closely approximate P in this space, and using these simple properties they determined the P-chromatic number of random graphs. 相似文献
8.
Götz Gelbrich 《Geometriae Dedicata》1994,51(3):235-256
We consider tilings ofR
n
by copies of a compact setA under the action of a crystallographic group, such that the union ofk suitably chosen tiles is affinely isomorphic toA. For dimensionn=2 we show that for eachk2 there is a finite number of isomorphy classes of such setsA which are homeomorphic to a disk. We give an algorithm which determines all disk-like tiles for a given group and numberk. The algorithm will be applied to the groupsp2 andp3 withk=3. 相似文献
9.
A crucial step in the Erdös-Rényi (1960) proof that the double-jump threshold is also the planarity threshold for random graphs is shown to be invalid. We prove that whenp=1/n, almost all graphs do not contain a cycle with a diagonal edge, contradicting Theorem 8a of Erdös and Rényi (1960). As a consequence, it is proved that the chromatic number is 3 for almost all graphs whenp=1/n.Research supported U.S. National Science Foundation Grants DMS-8303238 and DMS-8403646. The research was conducted on an exchange visit by Professor Wierman to Poland supported by the national Academy of Sciences of the USA and the Polish Academy of Sciences. 相似文献
10.
Proposed as a general framework, Liu and Yu [Generalization of matching extensions in graphs, Discrete Math. 231 (2001) 311-320.] introduced (n,k,d)-graphs to unify the concepts of deficiency of matchings, n-factor-criticality and k-extendability. Let G be a graph and let n,k and d be non-negative integers such that n+2k+d?|V(G)|-2 and |V(G)|-n-d is even. If when deleting any n vertices from G, the remaining subgraph H of G contains a k-matching and each such k-matching can be extended to a defect-d matching in H, then G is called an (n,k,d)-graph. Liu and Yu's Papee's paper, the recursive relations for distinct parameters n,k and d were presented and the impact of adding or deleting an edge also was discussed for the case d=0. In this paper, we continue the study begun by Liu and Yu and obtain new recursive results for (n,k,d)-graphs in the general case d?0. 相似文献
11.
Hajós conjectured that everys-chromatic graph contains a subdivision ofK
s, the complete graph ons vertices. Catlin disproved this conjecture. We prove that almost all graphs are counter-examles in a very strong sense. 相似文献
12.
For any graphG and numbern≧1 two functionsf, g fromV(G) into {1, 2, ...,n} are adjacent if for all edges (a, b) ofG, f(a) ≠g(b). The graph of all such functions is the colouring graph ℒ(G) ofG. We establish first that χ(G)=n+1 implies χ(ℒ(G))=n iff χ(G ×H)=n+1 for all graphsH with χ(H)≧n+1. Then we will prove that indeed for all 4-chromatic graphsG χ(ℒ(G))=3 which establishes Hedetniemi’s [3] conjecture for 4-chromatic graphs.
This research was supported by NSERC grant A7213 相似文献
13.
Yasutsugu Fujita 《manuscripta mathematica》2005,118(3):339-360
Let E be an elliptic curve over Q and p a prime number. Denote by Qp,∞ the Zp-extension of Q. In this paper, we show that if p≠3, then where E(Qp,∞)(2) is the 2-primary part of the group E(Qp,∞) of Qp,∞-rational points on E. More precisely, in case p=2, we completely classify E(Q2,∞)(2) in terms of E(Q)(2); in case p≥5 (or in case p=3 and E(Q)(2)≠{O}), we show that E(Qp,∞)(2)=E(Q)(2). 相似文献
14.
Minimal codewords were introduced by Massey (Proceedings of the 6th Joint Swedish-Russian International Workshop on Information
Theory, pp 276–279, 1993) for cryptographical purposes. They are used in particular secret sharing schemes, to model the access
structures. We study minimal codewords of weight smaller than 3 · 2
m−r
in binary Reed–Muller codes RM(r, m) and translate our problem into a geometrical one, using a classification result of Kasami and Tokura (IEEE Trans Inf Theory
16:752–759, 1970) and Kasami et al. (Inf Control 30(4):380–395, 1976) on Boolean functions. In this geometrical setting, we
calculate numbers of non-minimal codewords. So we obtain the number of minimal codewords in the cases where we have information
about the weight distribution of the code RM(r, m). The presented results improve previous results obtained theoretically by Borissov et al. (Discrete Appl Math 128(1), 65–74,
2003), and computer aided results of Borissov and Manev (Serdica Math J 30(2-3), 303–324, 2004). This paper is in fact an
extended abstract. Full proofs can be found on the arXiv. 相似文献
15.
H. -J. Voss 《Combinatorica》1985,5(3):261-269
A graph is said to have propertyP
k
if in eachk-colouring ofG using allk colours there arek independent vertices having all colours. An (unpublished) suggestion of P. Erdős is answered in the affirmative: For eachk≧3 there is a k-critical graph withP
k
. With the aid of a construction of T. Gallaik-chromatic graphs (k≧7) withP
k
orP
k+1 of arbitrarily high connectivity are obtained. The main result is: Eachk-chromatic graph (k≧3) of girth ≧6 hasP
k
or is a circuit of length 7.
Dedicated to Paul Erdős on his seventieth birthday 相似文献
16.
Pablo Spiga 《Journal of Algebraic Combinatorics》2007,26(3):343-355
In this paper we prove that an elementary Abelian p-group of rank 4p−2 is not a CI(2)-group, i.e. there exists a 2-closed transitive permutation group containing two non-conjugate regular elementary Abelian
p-subgroups of rank 4p−2, see Hirasaka and Muzychuk (J. Comb. Theory Ser. A 94(2), 339–362, 2001). It was shown in Hirasaka and Muzychuk (loc cit) and Muzychuk (Discrete Math. 264(1–3), 167–185, 2003) that this is related to the problem of determining whether an elementary Abelian p-group of rank n is a CI-group.
As a strengthening of this result we prove that an elementary Abelian p-group E of rank greater or equal to 4p−2 is not a CI-group, i.e. there exist two isomorphic Cayley digraphs over E whose corresponding connection sets are not conjugate in Aut E.
This research was supported by a fellowship from the Pacific Institute for the Mathematical Sciences. 相似文献
17.
Gábor Tardos 《Journal of Combinatorial Theory, Series A》2005,111(2):266-288
We say that a 0-1 matrix A avoids another 0-1 matrix (pattern) P if no matrix P′ obtained from P by increasing some of the entries is a submatrix of A. Following the lead of (SIAM J. Discrete Math. 4 (1991) 17-27; J. Combin. Theory Ser. A 55 (1990) 316-320; Discrete Math. 103 (1992) 233-251) and other papers we investigate n by n 0-1 matrices avoiding a pattern P and the maximal number ex(n,P) of 1 entries they can have. Finishing the work of [8] we find the order of magnitude of ex(n,P) for all patterns P with four 1 entries. We also investigate certain collections of excluded patterns. These sets often yield interesting extremal functions different from the functions obtained from any one of the patterns considered. 相似文献
18.
A random bipartite graphG(n, n, p) is obtained by taking two disjoint subsets of verticesA andB of cardinalityn each, and by connecting each pair of verticesaA andbB by an edge randomly and independently with probabilityp=p(n). We show that the choice number ofG(n, n, p) is, almost surely, (1+o(1))log2(np) for all values of the edge probabilityp=p(n), where theo(1) term tends to 0 asnp tends to infinity.Research supported in part by a USA-Israeli BSF grant, a grant from the Israel Science Foundation, a Sloan Foundation grant No. 96-6-2 and a State of New Jersey grant.Research supported by an IAS/DIMACS Postdoctoral Fellowship. 相似文献
19.
A conjecture of Toft [17] asserts that any 4-critical graph (or equivalently, every 4-chromatic graph) contains a fully odd subdivision ofK
4. We show that if a graphG has a degree three nodev such thatG-v is 3-colourable, then eitherG is 3-colourable or it contains a fully oddK
4. This resolves Toft's conjecture in the special case where a 4-critical graph has a degree three node, which is in turn used to prove the conjecture for line-graphs. The proof is constructive and yields a polynomial algorithm which given a 3-degenerate graph either finds a 3-colouring or exhibits a subgraph that is a fully odd subdivision ofK
4. (A graph is 3-degenerate if every subgraph has some node of degree at most three.) 相似文献
20.
Michael A. Henning 《Quaestiones Mathematicae》2018,41(5):693-706
A set S of vertices in a graph G is a packing if the vertices in S are pairwise at distance at least 3 apart in G. The packing number of G, denoted by ρ(G), is the maximum cardinality of a packing in G. Favaron [Discrete Math. 158 (1996), 287–293] showed that if G is a connected cubic graph of order n different from the Petersen graph, then ρ(G) ≥ n/8. In this paper, we generalize Favaron’s result. We show that for k ≥ 3, if G is a connected k-regular graph of order n that is not a diameter-2 Moore graph, then ρ(G) ≥ n/(k2 ? 1). 相似文献