摘要:

AbstractStar chromatic number, introduced by A. Vince, is a natural generalization of chromatic number. We consider the question, “When is χ*<χ?” We show that χ*<χ if and only if a particular digraph is acyclic and that the decisioin problem associated with this question is probably not in NP though it is both NP‐hard and NP‐easy. © 1993 John Wil

ISSN:0364-9024    

DOI:10.1002/jgt.3190170202

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractWe consider four models of random directed multigraphs withnlabeled vertices of out‐degreed. First we establish formal relationships between our models with respect to exact and asymptotic (asn→ ∞) probabilities of possessing a graph monotone property. We also study the asymptotic behavior of the strength of connectivity of the underlying simple graphs whend= o(n). © 1993 John Wiley&Son

ISSN:0364-9024    

DOI:10.1002/jgt.3190170203

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractIn this paper, we show that the edge set of a cubic graph can always be partitioned into 10 subsets, each of which induces a matching in the graph. This result is a special case of a general conjecture made by Erdös and Nešetřil: For eachd≥ 3, the edge set of a graph of maximum degreedcan always be partitioned into [5d2/4] subsets each of which induces a matching. © 1993 John Wiley&Sons

ISSN:0364-9024    

DOI:10.1002/jgt.3190170204

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractA characterization is established for a graphGto have a Hamilton cycle inG×K2, the prism overG. Moreover, it is shown that every 3‐connected graph has a 2‐connected spanning bipartite subgraph. Using this result, the existence of a Hamilton cycle in the prism over every 3‐connected cubic graph is established. Further, the existence of a Hamilton cycle in the prism over a cubic 2‐connected graph is also discussed. Earlier results in this direction are shown to be particular cases of the results obtained here. © 1993 John Wiley&

ISSN:0364-9024    

DOI:10.1002/jgt.3190170205

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractWe show that each partial order ≤ of height 2 can be represented by spheres in Euclidean space, where inclusion represents ≤. If each element has at mostkelements under it, we can do this in 2k− 1‐dimensional space. This extends a result (and a method) of Scheinerman for the casek= 2. © 1993 John Wiley&S

ISSN:0364-9024    

DOI:10.1002/jgt.3190170206

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractFor a graphGwhose number of edges is divisible byk, letR(G,Zk) denote the minimum integerrsuch that for every functionf:E(Kr) ↦Zkthere is a copyG1ofGinKrso that Σe∈E(G1)f(e)= 0 (inZk). We prove that for every integerk1R(Kn, Zk)≤n+ O(k3logk) providednis sufficiently large as a function ofkandkdivides ( 2n). If, in addition,kis an odd prime‐power thenR(Kn, Zk)≤n+ 2k‐ 2 and this is tight ifkis a prime that dividesn. A related result is obtained for hypergraphs. It is further shown that for every graphGonnvertices with an even number of edgesR(G,Z2)≤n+ 2. This estimate is sharp. © 1993 Joh

ISSN:0364-9024    

DOI:10.1002/jgt.3190170207

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractThe irredundant Ramsey numbers(m, n)is the smallestNsuch that in every red‐blue coloring of the edges ofKN, either the blue graph contains anm‐element irredundant set or the red graph contains ann‐element irredundant set. The definition of the mixed Ramsey numbert(m, n)differs froms(m, n)in that then‐element irredundant set is replaced by ann‐element independent set. We prove asymptotic lower bounds fors(n, n)andt(m, n)(withmfixed andnlarge) and a general upper bound fort(3,n). © 1993 John Wiley

ISSN:0364-9024    

DOI:10.1002/jgt.3190170208

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractThe notion ofp‐proportional graphs comes from the study of subgraph counts in random graphs, where thep‐proportional graphs occur as exceptional cases in a central limit theorem. In this paper we show thatp‐proportional graphs exist for all rationalp, 0

ISSN:0364-9024    

DOI:10.1002/jgt.3190170209

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractThechordalityof a graphG= (V, E) is defined as the minimumksuch that we can writeE=E1∩ … ∩Ekwith each (V, Ei) a chordal graph. We present several results bounding the value of this generalization of boxicity. Our principal result is that the chordality of a graph is at most its tree width. In particular, series‐parallel graphs have chordality at most 2. Potential strengthenings of this statement fail in that there are planar graphs with chordality 3 and series‐parallel graphs with boxicity 3. © 1993 John Wiley

ISSN:0364-9024    

DOI:10.1002/jgt.3190170210

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractThe edge‐toughnessT1(G) of a graphGis defined aswhere the minimum is taken over every edge‐cutsetXthat separatesGinto ω (G‐X) components. We determine this quantity for some special classes of graphs that also gives the arboricity of these graphs. We also give a simpler proof to the following result of Peng et al.: For any positive integersr, s satisfyingr/2

ISSN:0364-9024    

DOI:10.1002/jgt.3190170211

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY