Geometric Achromatic and Pseudoachromatic Indices

The pseudoachromatic index of a graph is the maximum number of colors that can be assigned to its edges, such that each pair of different colors is incident to a common vertex. If for each vertex its incident edges have different color, then this maximum is known as achromatic index. Both indices have been widely studied. A geometric graph is a graph drawn in the plane such that its vertices are points in general position, and its edges are straight-line segments. In this paper we extend the notion of pseudoachromatic and achromatic indices for geometric graphs, and present results for complete geometric graphs. In particular, we show that for n points in convex position the achromatic index and the pseudoachromatic index of the complete geometric graph are \(\lfloor \frac{n^2+n}{4} \rfloor \).     

图的区间边着色的收缩图方法

图G的一个用了颜色1,2,…,t的边着色称为区间t-着色,如果所有t种颜色都被用到,并且关联于G的同一个顶点的边上的颜色是各不相同的,且这些颜色构成了一个连续的整数区间.G称作是可区间着色的,如果对某个正整数t,G有一个区间t-着色.所有可区间着色的图构成的集合记作■.对图G∈■,使得G有一个区间t-着色的t的最小值和最大值分别记作ω(G)和W(G).现给出了图的区间着色的收缩图方法.利用此方法,我们对双圈图G∈■,证明了ω(G)=△(G)或△(G)+1,并且完全确定了ω(G)=△(G)及ω(G)=△(G)+1的双圈图类.     

Computing simple paths among obstacles

Given a set X of points in the plane, two distinguished points s,tX, and a set Φ of obstacles represented by line segments, we wish to compute a simple polygonal path from s to t that uses only points in X as vertices and avoids the obstacles in Φ. We present two results: (1) we show that finding such simple paths among arbitrary obstacles is NP-complete, and (2) we give a polynomial-time algorithm that computes simple paths when the obstacles form a simple polygon P and X is inside P. Our algorithm runs in time O(m²n²), where m is the number of vertices of P and n is the number of points in X.     

Eulerian straight ahead cycles in drawings of complete bipartite graphs

Straight ahead cycles in drawings of graphs pass all vertices leaving the same number of edges on each side. For complete bipartite graphs K_2r,2s, drawings with straight ahead Eulerian cycles and with straight ahead 4-cycles are constructed.     

On fat partitioning, fat covering and the union size of polygons

The complexity of the contour of the union of simple polygons with n vertices in total can be O(n²) in general. A notion of fatness for simple polygons is introduced that extends most of the existing fatness definitions. It is proved that a set of fat polygons with n vertices in total has union complexity O(n log log n), which is a generalization of a similar result for fat triangles (Matou ek et al., 1994). Applications to several basic problems in computational geometry are given, such as efficient hidden surface removal, motion planning, injection molding, and more. The result is based on a new method to partition a fat simple polygon P with n vertices into O(n) fat convex quadrilaterals, and a method to cover (but not partition) a fat convex quadrilateral with O(l) fat triangles. The maximum overlap of the triangles at any point is two, which is optimal for any exact cover of a fat simple polygon by a linear number of fat triangles.     

An improved upper bound for Ramsey number N (3, 3, 3, 3; 2)

The Ramsey number N(3,3,3,3; 2) is the smallest integer n such that each 4-coloring by edges of the complete graph on n vertices contains monochromatic triangles. It is well known that 51 ≤ N(3, 3, 3, 3; 2) ≤ 65. Here we prove that N(3, 3, 3, 3; 2) ≤ 64.     

Set to set broadcasting in communication networks

Suppose G = (V,E) is a graph whose vertices represent people and edges represent telephone lines between pairs of people. Each person knows a unique message and is ignorant of the messages of other people at the beginning. These messages are then spread by telephone calls. In each call, two people exchange all information they have so far in exactly one unit of time. Suppose A and B are two nonempty subsets of V. The main purpose of this paper is to study the minimum number b(A,B,G) of telephone calls by which A broadcasts to B; and the minimum time t(A,B,G) such that A broadcasts to B. In particular, we give an exact formula for b(A,B,K_n) and linear-time algorithms for computing b(A,B,T) and t(A,B,T) of a tree T.     

Characterization of acceptance sets for co-monotone risk measures

We present a geometric characterization of acceptance sets for monotone, co-monotone and convex risk measures on finite state spaces. Geometrically, such acceptance sets can be represented by convex polygons with edges only on certain hyperplanes. We also provide some lower dimensional examples, and study acceptance sets for value at risk and expected shortfall.     

On the harmonious coloring of collections of graphs

The hermonious coloring number of the graph G, HC(G), is the smallest number of colors needed to label the vertices of G such that adjacent vertices received different colors and no two edges are incident with the same color pair. In this paper, we investigate the HC-number of collections of disjoint paths, cycles, complete graphs, and complete bipartite graphs. We determine exact expressions for the HC-number of collections of paths and 4m-cycles. © 1995, John Wiley & Sons, Inc.     

About the upper chromatic number of a co-hypergraph

A mixed hypergraph consists of two families of subsets: the edges and the co-edges. In a coloring every co-edge has at least two vertices of the same color, and every edge has at least two vertices of different colors. The largest and smallest possible number of colors in a coloring is termed the upper and lower chromatic numbers, respectively. In this paper we investigate co-hypergraphs i.e., the hypergraphs with only co-edges, with respect to the property of coloring. The relationship between the lower bound of the size of co-edges and the lower bound of the upper chromatic number is explored. The necessary and sufficient conditions for determining the upper chromatic numbers, of a co-hypergraph are provided. And the bounds of the number of co-edges of some uniform co-hypergraphs with certain upper chromatic numbers are given.     

Cartographic line simplification and polygon CSG formulæ in O(n log n) time

A constructive solid geometry (CSG) conversion for a polygon takes a list of vertices and produces a formula representing the polygon as an intersection and union of primitive halfspaces. The cartographers' favorite line simplification algorithm recursively selects from a list of data points those to be used to represent a linear feature, such as a coastline, on a map. By using a data structure that maintains convex hulls of polygonal lines under splits, both were known to have O(n log n) time solutions in the worst-case. This paper shows that both are easier than sorting by presenting an O(n log^* n) algorithm for maintaining convex hulls under splits at extreme points. It opens the question of whether there are practical, linear-time solutions to these problems.     

Packing trees into planar graphs

In this study, we provide methods for drawing a tree with n vertices on a convex polygon, without crossings and using the minimum number of edges of the polygon. We apply the results to obtain planar packings of two trees in some specific cases. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 172–181, 2002     

On the bounded domination number of tournaments

In a simple digraph, a star of degree t is a union of t edges with a common tail. The k-domination number γ_k(G) of digraph G is the minimum number of stars of degree at most k needed to cover the vertex set. We prove that γ_k(T)=n/(k+1) when T is a tournament with n14k lg k vertices. This improves a result of Chen, Lu and West. We also give a short direct proof of the result of E. Szekeres and G. Szekeres that every n-vertex tournament is dominated by at most lg n−lglg n+2 vertices.     

Geometric Graphs with No Three Disjoint Edges

A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position and edges are represented by straight line segments. We show that a geometric graph on n vertices with no three pairwise disjoint edges has at most 2.5n edges. This result is tight up to an additive constant.     

4一致反超图的最小边数问题

混合超图是在超图的基础上添加一个反超边得到的图．超边和反超边的区别主要体现在着色要求上．在着色中,要求每一超边至少要有两个点着不同的颜色,而每一反超边至少有两个点着相同的颜色．最大最小颜色数分别称为混合超图的上色数和下色数。本文主要研究反超图,即只含反超边的超图。讨论了上色数为3的4一致超图的最小边数问题．给出了上色数为3的4一致反超图的最小边数的一个上界和一个下界．     

A Note on Strong Edge Coloring of Sparse Graphs

A strong edge coloring of a graph is a proper edge coloring where the edges at distance at most 2 receive distinct colors. The strong chromatic index χ'_s(G) of a graph G is the minimum number of colors used in a strong edge coloring of G. In an ordering Q of the vertices of G, the back degree of a vertex x of G in Q is the number of vertices adjacent to x, each of which has smaller index than x in Q. Let G be a graph of maximum degree Δ and maximum average degree at most 2 k. Yang and Zhu [J. Graph Theory, 83, 334–339(2016)] presented an algorithm that produces an ordering of the edges of G in which each edge has back degree at most 4 kΔ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤ 4 kΔ-2 k + 1. In this note, we improve the algorithm of Yang and Zhu by introducing a new procedure dealing with local structures. Our algorithm generates an ordering of the edges of G in which each edge has back degree at most(4 k-1)Δ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤(4 k-1)Δ-2 k + 1.     

最大度为7 且不含带弦5- 圈的平面图是8- 全可染的

若能用k种颜色给图的顶点和边同时进行染色使得相邻或相关联的元素(顶点或边) 染不同的色, 则称这个图是k- 全可染的. 显然, 给最大度为Δ的图进行全染色, 至少要用Δ + 1 种不同的色.本文证明最大度为7 且不含带弦5- 圈的平面图是8- 全可染的. 这一结果进一步拓广了(Δ+1)- 全可染图类.     

Orientations with single source and sink

Let G be a graph and s, t a pair of vertices of it. Linear time algorithms are formulated for finding orientations D of G such that D has a unique source s and sink t or D has unique vertices s and t of in and outdegree zero, respectively. The variation which requires D to be additionally acyclic is also considered. Necessary and sufficient conditions for the existence of the orientations are described.     

The mixed volume optimization problem

The mixed volume optimization problem is to determine the point of duality Q for a given convex set K that minimizes the “mixed volume” of the associated polar set (K^*;Q). In the plane, the mixed volumes translate as the area and length; in space, the mixed volumes include the volume, surface area, and mean width. In this paper, the geometric optimization problems associated with minimizing mixed volumes are examined from two perspectives: enumerative search and symbolic computation. The problem of minimizing the polar area through an enumerative search is first considered. The dual polygon (P_m^*;Q) is constructed for an arbitrary point of duality QP_m° by using an algebraic correspondence between the edges of P_m and the vertices of (P_m^*;Q), and the area of (P_m^*;Q), A(P^*_m;Q), is calculated and minimized using naive search techniques. A result due to Santaló is applied to verify the minimizing solution, and computational tests are described for various classes of randomly generated polygons. Statistical evidence indicates that a “good” approximation to the minimum area polar polygon occurs when the duality point is located at the center-of-gravity of P_m. The polar area problem is then investigated using symbolic procedures. Explicit symbolic expressions for the polar area and length functionals are computed and solved directly using the differential optimality conditions and Newton's iterative method of solution. The mixed volume and surface area functionals are formulated and solved using numerical products, and the mean width functional is described. Examples are used throughout to illustratethe methodology.     

Menger-type theorems with restrictions on path lengths

If the paths of length s, joining two non-adjacent vertices u, υ of a graph cannot be destroyed by deleting less than t vertices, then there are at least t internally vertex-disjoint paths joining u and υ, each having length less than . Some constructions show that using paths of length at least s/t−1^t might be necessary.