摘要:

AbstractThem‐chromatic numberχm(G) of a graphGis the fewest colors needed so each node hasmcolors and no color appears on adjacent nodes. Thefractionalchromatic number is χ*(G)=limm→∞χm(G)/m. Letm(G) be the leastmso that χ* (G) = χm(G)/m. Fornnode graphs, Chvátal, Garey and Johnson showedm(G) ≦nn/2and gave example, wherem(G) is asymptotically. This note gives examples wherem(G) is asymptotically λn, where λ ≈︁ 1.346193. © 1995

ISSN:0364-9024    

DOI:10.1002/jgt.3190200403

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

年代:1995

数据来源: WILEY

摘要:

AbstractThe fractional chromatic number of a graphGis the infimum of the total weight that can be assigned to the independent sets ofGin such a way that, for each vertexvofG, the sum of the weights of the independent sets containingvis at least 1.In this note we give a graph a graph whose fractional chromatic number is strictly greater than the supremum of the fractional chromatic numbers of its finite subgraphs. This answers a question of Zhu. We also give some grphs for which the fractional chromatic number is not attined, answering another of Zhu. © 1995 John Wiley&Sons, Inc

ISSN:0364-9024    

DOI:10.1002/jgt.3190200404

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

年代:1995

数据来源: WILEY

摘要:

AbstractIt is shown that if in a simple graphGof ordernthe sum of degrees of any three pairwise non‐adjacent vertices is at leastn, then there are two cycles (or one cycle and an edge or a vertex) ofGFthat contain all the vertices. © 1995 John Wiley&Sons, I

ISSN:0364-9024    

DOI:10.1002/jgt.3190200405

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

年代:1995

数据来源: WILEY

摘要:

AbstractIn this paper, we investigate the Hamiltonicity ofK1,r‐free graphs with some degree conditions. In particular, letGbe ak‐connected grph of ordern≧3 which isK1,4‐free. Iffor every independent set {v0,v1, …,vk} thenGis hamiltonian. We use an upper bound for the independence number ofK1,r‐free graphs to extent the above result toK1,r‐free graphs. Hamiltonian connected and, more generally,q‐edge hamiltonian properties are studied here as well. © 1995 John

ISSN:0364-9024    

DOI:10.1002/jgt.3190200406

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

年代:1995

数据来源: WILEY

摘要:

AbstractFor any plane graphGthe number of edges in a minimum edge covering of the faces ofGis at most the vertex independence number ofGand the numbre of vertices in a minimum vertex covering of the faces ofGis at most the edge independence number ofG. © 1995 John Wiley&Sons, Inc

ISSN:0364-9024    

DOI:10.1002/jgt.3190200407

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

年代:1995

数据来源: WILEY

摘要:

AbstractM. Matthews and D. Sumner have proved that ofGis a 2‐connected claw‐free graph of ordernsuch that δ ≧ (n− 2)/3, thenGis hamiltonian. We prove that the bound for the minimum degree δ can be reduced ton/4 under the additional condition thatGis not inF, whereFis the set of all graphs defined as follows: any graphHinFcan be decomposed into three vertex disjoint subgraphsH1,H2,H3such that, whereui,viϵV(Hi),ujvjϵV(Hj) 1 ϵi≦j≦ 3. Examples are given to show that the boundn/4 is sharp. © 1995 Joh

ISSN:0364-9024    

DOI:10.1002/jgt.3190200408

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

年代:1995

数据来源: WILEY

摘要:

AbstractLetGbe a 2‐connected claw‐free graph onnvertices, and letHbe a subgraph ofG. We prove thatGhas a cycle containing all vertices ofHwhenever α3(H) ≧ κ(G), where α3(H) denotes the maximum number of vertices ofHthat are pairwise at distance at least three inG, and κ(G) denotes the connectivity ofG. This result is an analog of a result from the thesis of Fournier, and generalizes the result of Zhang thatGis hamiltonian if the degree sum of any κ(G) + 1 pairwise nonadjacent vertices is at leastn− κ(G). © 1995 John W

ISSN:0364-9024    

DOI:10.1002/jgt.3190200409

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

年代:1995

数据来源: WILEY

摘要:

AbstractA homomorphism of a digraph to another digraph is an edgepreserving vertex mapping. A local tournament is a digraph in which the inset as well as the outset of each vertex induces a tournament. Thus acyclic local tournaments generalize both directed paths and transitive tournaments. In both these cases there is a simple characterization of homomorphic preimages. Namely, ifHis a directed path, or a transitive tournament, thenGadmits a homomorphism toHif and only if each oriented path which admits a homomorphism toGalso admits a homomorphism toH. We prove that this result holds for all acyclic local tournaments. © 1995 John Wiley&Sons, Inc

ISSN:0364-9024    

DOI:10.1002/jgt.3190200410

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

年代:1995

数据来源: WILEY

摘要:

AbstractThe main result of this paper completely settles Bermond's conjecture for bipartite graphs of odd degree by proving that ifGis a bipartite (2k+ 1)‐regular graph that is Hamilton decomposable, then the line graph,L(G), ofGis also Hamilton decomposable. A similar result is obtained for 5‐regular graphs, thus providing further evidence to support Bermond's conjecture. © 1995 John Wiley&Sons,

ISSN:0364-9024    

DOI:10.1002/jgt.3190200411

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

年代:1995

数据来源: WILEY

摘要:

AbstractWe investigate tree decompositions (T,(Xt)tϵV(T)) whose width is “close to optimal” and such that all the subtrees ofTinduced by the vertices of the graph are “small.” We prove the existence of such decompositions for various interpretations of “close to optimal” and “small.” As a corollary of these results, we prove that the dilation of a graph is bounded by a logarithmic function of the congestion of the graph thereby settling a generalization of a conjecture of Bienstock. © 1995 Joh

ISSN:0364-9024    

DOI:10.1002/jgt.3190200412

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

年代:1995

数据来源: WILEY