Coloring mixed hypertrees

A mixed hypergraph is a triple (V,C,D) where V is its vertex set and C and D are families of subsets of V, called C-edges and D-edges, respectively. For a proper coloring, we require that each C-edge contains two vertices with the same color and each D-edge contains two vertices with different colors. The feasible set of a mixed hypergraph is the set of all k's for which there exists a proper coloring using exactly k colors. A hypergraph is a hypertree if there exists a tree such that the edges of the hypergraph induce connected subgraphs of the tree.We prove that feasible sets of mixed hypertrees are gap-free, i.e., intervals of integers, and we show that this is not true for precolored mixed hypertrees. The problem to decide whether a mixed hypertree can be colored by k colors is NP-complete in general; we investigate complexity of various restrictions of this problem and we characterize their complexity in most of the cases.     

Coloring axis-parallel rectangles

For every k and r, we construct a finite family of axis-parallel rectangles in the plane such that no matter how we color them with k colors, there exists a point covered by precisely r members of the family, all of which have the same color. For r=2, this answers a question of S. Smorodinsky [S. Smorodinsky, On the chromatic number of some geometric hypergraphs, SIAM J. Discrete Math. 21 (2007) 676-687].     

Coloring complexes and arrangements

Steingrimsson’s coloring complex and Jonsson’s unipolar complex are interpreted in terms of hyperplane arrangements. This viewpoint leads to short proofs that all coloring complexes and a large class of unipolar complexes have convex ear decompositions. These convex ear decompositions impose strong new restrictions on the chromatic polynomials of all finite graphs. Similar results are obtained for characteristic polynomials of submatroids of type ℬ _n arrangements. The first author was supported by NSF grant DMS-0500638. The second author was supported by NSF grant DMS-0245623.     

Coloring BIBDs with block size 4

It is shown that for each integer m ≥ 1 there exists a lower bound, v_m, with the property that for all v ≥ v_m with v ≡ 1, 4 (mod 12) there exists an m-chromatic S(2, 4, v) design. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 403–409, 1998     

Coloring by two-way independent sets

The paper stems from an attempt to investigate a somewhat mysterious phenomenon: conditions which suffice for the existence of a “large” set satisfying certain conditions (e.g., a large independent set in a graph) often suffice (or at least are conjectured to suffice) for the existence of a covering of the ground set by few sets satisfying these conditions (in the example of independent sets in a graph this means that the graph has small chromatic number). We consider two conjectures of this type, on coloring by sets which are “two-way independent”, in the sense of belonging to a matroid and at the same time being independent in a graph sharing its ground set with the matroid. We prove these conjectures for matroids of rank 2. We also consider dual conjectures, on packing bases of a matroid, which are independent in a given graph.     

Region-Fault Tolerant Geometric Spanners

We introduce the concept of region-fault tolerant spanners for planar point sets and prove the existence of region-fault tolerant spanners of small size. For a geometric graph on a point set P and a region F, we define to be what remains of after the vertices and edges of intersecting F have been removed. A  -fault tolerant t-spanner is a geometric graph  on P such that for any convex region F, the graph is a t-spanner for , where is the complete geometric graph on P. We prove that any set P of n points admits a -fault tolerant (1+ε)-spanner of size for any constant ε>0; if adding Steiner points is allowed, then the size of the spanner reduces to  , and for several special cases, we show how to obtain region-fault tolerant spanners of size without using Steiner points. We also consider fault-tolerant geodesic t -spanners: this is a variant where, for any disk D, the distance in between any two points u,v∈P∖D is at most t times the geodesic distance between u and v in ℝ²∖D. We prove that for any P, we can add Steiner points to obtain a fault-tolerant geodesic (1+ε)-spanner of size  . M.A. Abam was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 612.065.307 and by the MADALGO Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation. M. de Berg was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301. M. Farshi was supported by Ministry of Science, Research and Technology of I.R. Iran. NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program.     

Solving the Minimum Weighted Integer Coloring Problem

In this paper, we present, as we are aware of, the first combinatorialalgorithm specifically designed for the minimum weighted integercoloring problem (MWIP). We test the algorithm on randomly generated graphs with integer weights uniformly drawn from intervals [1, 1], [1, 2], [1, 5], [1, 10], [1, 15], and [1, 20]. We also use theproposed algorithm to test the quality of a simple, yet effectiveheuristic for the MWIP in the literature. We have observed from our test that: i( the algorithm is able to solve MWIP on graphs of up to 20 vertices when the average vertex weights is not too large; ii( The relative gap between the simple heuristic solutions and the optimal solution seems to decrease as the average vertex weight increases. A rough comparison with the state-of-the-art methods for the minimum unweighted coloring problem seems to suggest the advantage of solving MWIP directly.     

An exact approach for the Vertex Coloring Problem

Given an undirected graph $G=(V,E)$, the Vertex Coloring Problem (VCP) requires to assign a color to each vertex in such a way that colors on adjacent vertices are different and the number of colors used is minimized. In this paper, we present an exact algorithm for the solution of VCP based on the well-known Set Covering formulation of the problem. We propose a Branch-and-Price algorithm embedding an effective heuristic from the literature and some methods for the solution of the slave problem, as well as two alternative branching schemes. Computational experiments on instances from the literature show the effectiveness of the algorithm, which is able to solve, for the first time to proven optimality, five of the benchmark instances in the literature, and reduce the optimality gap of many others.     

Coloring arcs of convex sets

In this note we consider Ramsey-type problems on graphs whose vertices are represented by the vertices of a convex polygon in the Euclidean plane. The edges of the graph are represented by the segments between the points of the polygon. The edges are arbitrarily colored by a fixed number of colors and the problem is to decide whether there exist monochromatic subgraphs of certain types satisfying some geometric conditions. We will give lower and upper bounds for these geometric Ramsey numbers for certain paths and cycles and also some exact values. It turns out that the particular type of the embedding is crucial for the growth rate of the corresponding geometric Ramsey numbers. In particular, the Ramsey numbers for crossing 4-cycles and t colors grow quadratically in t, while for convex 4-cycles they grow at least exponentially.     

Coloring permutation graphs in parallel

A coloring of a graph G is an assignment of colors to its vertices so that no two adjacent vertices have the same color. We study the problem of coloring permutation graphs using certain properties of the lattice representation of a permutation and relationships between permutations, directed acyclic graphs and rooted trees having specific key properties. We propose an efficient parallel algorithm which colors an n-node permutation graph in O(log² n) time using O(n²/log n) processors on the CREW PRAM model. Specifically, given a permutation π we construct a tree T^*[π], which we call coloring-permutation tree, using certain combinatorial properties of π. We show that the problem of coloring a permutation graph is equivalent to finding vertex levels in the coloring-permutation tree.     

The Vertex Coloring Problem and its generalizations

This is a summary of the author’s PhD thesis supervised by Paolo Toth and defended on 29 May 2007 at the Università di Bologna. The thesis is written in English and is available from the author upon request. The first part of this work deals with the Vertex Coloring Problem and its generalizations, for which models, bounds and algorithms are proposed. The Second Part is dedicated to a different problem on graphs, namely a Routing Problem in telecommunication networks where not only the efficiency, but also the fairness of the solution is considered.      

A Note on Adjacent Strong Edge Coloring of K（n,m）

In this paper, we prove that the adjacent strong edge chromatic number of a graph K（n,m） is n ＋ 1, with n ≥ 2, m ≥ 1.     

关于一类几何极值问题

设平面上边长为１和２的闭矩形区域为Ｒ，Ｓ是Ｒ上一个有限点集，ｆ（Ｓ）是Ｓ中任意两点之间的最小距离，ｆＲ（ｎ）＝ｍａｘｆ（Ｓ），本文给出了当２≤ｎ≤６时，ｆＲ（ｎ）的精确值以及相应的图形．     

Geometric Completeness of Distribution Spaces

This paper introduces a notion of geometric completeness for spaces of distributions, modelled after the notion of a complete variety in algebraic geometry. It is related to the following elimination problem for systems of PDE: consider the set of homogeneous solutions of a system of PDE in some space of distributions. When is the projection of this set onto some of its coordinates also the set of homogeneous solutions of a system of PDE?     

On Some L-extensions of Dimensions of Topological Spaces

The concepts of covering dimension,small inductive dimension and large inductive dimension for topological spaces are extended to L-topological spaces using the quasi-coincidence relation.Besides getting some characterizations,it is also seen that all these characterizations are good in the sense of Lowen.     

Geometric automorphism groups of graphs

Constructing symmetric drawings of graphs is NP-hard. In this paper, we present a new method for drawing graphs symmetrically based on group theory. More formally, we define an n-geometric automorphism group as a subgroup of the automorphism group of a graph that can be displayed as symmetries of a drawing of the graph in n dimensions. Then we present an algorithm to find all 2- and 3-geometric automorphism groups of a given graph. We implement the algorithm using Magma [〈http://magma.maths.usyd.edu.au〉] and the experimental results show that our approach is very efficient in practice. We also present a drawing algorithm to display 2- and 3-geometric automorphism groups.     

Fuzzy正项几何规划的直接算法

将Fuzzy正项几何规划化的一变量有上、下界限制的Fuzzy正项几何规划,利用Fuzzy几何不等式,又将该变量有上、下界限制的Fuzzy正项几何规划化为单项Fuzzy正项几何规划,提出基于Fuzzy值集割平面法的两种直接算法,并通过一个数值例证实该方法的有效性。     

几何随机变量的卷积

使用组合数学与概率论的方法研究了几何随机变量的卷积.