摘要:

AbstractWe show that if a graph has maximum degreedand crossing numberk, its rectilinear crossing number is at mostO(dk2). Hence for graphs of bounded degree, the crossing number and the rectilinear crossing number are bounded as functions of one another. We also obtain a generalization of Tutte's theorem on convex embeddings of 3‐connected plane graphs. © 1929 John Wiley&Sons, I

ISSN:0364-9024    

DOI:10.1002/jgt.3190160502

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

年代:1992

数据来源: WILEY

摘要:

AbstractA signed graph Σ consists of a graph and a sign labeling of its edges. A polygon in Σ is “balanced” if its sign product is positiive. A signed graph is “orientatio embedded” in a surface if it is topologically embedded and a polygon is balanced precisely when traveling once around it preserves orientation. We explore the extension to orientation embedding of the ordinary theory of graph embedding. Letd(Σ) be the demigenus (= 2 ‐x(S)) of the unique smallest surfaceSin which Σ has an orientation embedding. Our main results are an easy one, that if Σ has connected components Σ1, Σ[2], ⃛, thend(Σ) =d(Σ1) + ⃛, and a hard one, that if Σ has a cut vertexvthat splits Σ into Σ1, Σ2, ⃛, thend(Σ) =d(Σ1) +d(Σ2) + ⃛ ‐δ, where δ depends on the number of Σiin whichvis “loopable”, that is, in whichd(Σi) =d(Σi with a negative loop added tov). This is as with ordinary orientable grpah embedidng except for the existence of the term δ in the cut‐vertex formula. Since loopability is crucial, we give some partial criteria for it. (A complete characterization seems difficult.) We conclude with an application to forbidden subgraphs and minors for orientation embeddability

ISSN:0364-9024    

DOI:10.1002/jgt.3190160503

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

年代:1992

数据来源: WILEY

摘要:

AbstractFor a fixed integernϵ ω, a graphGof chromatic number greater thannis called persistent if for alln+ 1‐chromatic graphsH, the productsG×Haren+ 1‐chromatic graphs. Wheter all graphs of chromatic number greater thannare persistent is a long‐standing open problem due to Hedetniemi. We call a graphGstrongly persistent ifGis persistent and the Hajos sum ofGwith any other persistent graphHis still persistent. This paper extends the class of known persistent graphs by proving the following results: IfGis constructed from copies ofKn+1by Hajos sums, adding vertices and edges and at most one contraction of nonadjacent vertices, thenGis strongly persistent. © 1929 John Wiley&

ISSN:0364-9024    

DOI:10.1002/jgt.3190160504

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

年代:1992

数据来源: WILEY

摘要:

AbstractWe prove that everyr‐biregular digraph withnvertices has its directed diamter bounded by (3n‐r‐ 3)/(r+1). We show that this bound is tight for directed as well as for undirected graphs. The upper bound remains valid for Eulerian digraphs with minimum outdegreer. © 1929 John Wiley&Son

ISSN:0364-9024    

DOI:10.1002/jgt.3190160505

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

年代:1992

数据来源: WILEY

摘要:

AbstractFor a graphbFwithout isolated vertices, letM(F;n) denote the minimum number of monochromatic copies ofFin any 2‐coloring of the edges ofKn. Burr and Rosta conjectured that\documentclass{article}\pagestyle{empty}\begin{document}$$ M(F;n) = \frac{{n^t }}{{2^{u - 1} a}} + O(n^{t - 1}) $$\end{document}whenFhas ordert, sizeu, andaautomorphisms. Independently, Sidorenko and Thomason have shown that the conjecture is false. We give families of graphsFof ordert, of sizeu, and withaautomorphisms where\documentclass{article}\pagestyle{empty}\begin{document}$$ \frac{{M(F;n)2^{u - 1} a}}{{n^t }} \to 0\,{\rm as}\,t \to \infty $$\end{document}.We show also that the asymptotic value ofM(F;n) is not solely a function of the order, size and number of automorphisms ofF. © 1929 John Wiley&Sons, I

ISSN:0364-9024    

DOI:10.1002/jgt.3190160506

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

年代:1992

数据来源: WILEY

摘要:

AbstractIt is proved that all classes of polygon trees are characterized by their chromatic polynomials, and a characterization is given of those polynominals that are chromatic polynomials of outerplanar graphs. The first result yields an alternative proof that outerplanar graphs are recognizable from their vertex‐deleted subgraphs. © 1929 John Wiley&Sons, I

ISSN:0364-9024    

DOI:10.1002/jgt.3190160507

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

年代:1992

数据来源: WILEY

摘要:

AbstractWe study a hierarchy of canonical representations of grpahs as subgraphs of cartesian products of graphs. This hierarchy starts with the isometric representation, includes the 2‐isometric represnetation, and ends with the cartesian prime factorization. We show that all three representations can be obtained inO(nm) time usingO(m) space, for graphs withnvertices andmedges. The algorithms have immediate parallel versions that usen3processors and run inO(log2n) time. © 1929 John Wiley&Sons, I

ISSN:0364-9024    

DOI:10.1002/jgt.3190160508

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

年代:1992

数据来源: WILEY

摘要:

AbstractLet

ISSN:0364-9024    

DOI:10.1002/jgt.3190160509

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

年代:1992

数据来源: WILEY

摘要:

AbstractIn this paper we discuss some estimates for upper bounds on a number of chromatic parameters of a multigraph. In particular, we show that the total chromatic number for ann‐order multigraph exceeds the chromatic index by the smallesttsuch thatt!>

ISSN:0364-9024    

DOI:10.1002/jgt.3190160510

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

年代:1992

数据来源: WILEY

摘要:

AbstractAn (s, t)‐directed star is a directed graph withs+t+ 1 vertices and s + t arcs; s vertices have indegree zero and outdegree one,thave indegree one and outdegree zero, and one has indegreesand outdegreet. An (s, t)‐directed star decomposition is a partition of the arcs of a complete directed graph of orderninto (s, t)‐directed starsx. We establish necessary and sufficient conditions ons, t, andnfor an (s, t)‐directed star decomposition of ordernt

ISSN:0364-9024    

DOI:10.1002/jgt.3190160511

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

年代:1992

数据来源: WILEY