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].     

WEIGHTED INEQUALITIES FOR THE GEOMETRIC MAXIMAL OPERATOR ON MARTINGALE SPACES

In this article, the authors introduce two operators-geometrical maximal operator Mo and the closely related limiting operator M0^＊, then they give sufficient conditions under which the equality M0=MM0^＊ holds, and characterize the equivalent relations between the weak or strong type weighted inequality and the property of W∞-weight or W∞^＊-weight for the geometrical maximal operator in the case of two-weight condition. What should be mentioned is that the new operator-the geometrical minimal operator is equal to the limitation of the minimal operator sequence, and the results for the minimal operator proved in [12] makes the proof elegant and evident.     

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 uniform hypergraphs with few colors

Let m(r, k) denote the minimum number of edges in an r‐uniform hypergraph that is not k‐colorable. We give a new lower bound on m(r, k) for fixed k and large r. Namely, we prove that if k ≥ 2ⁿ, then m(r, k) ≥ ?(k)k^r(r/ln r)^n/(n+1). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

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.     

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.     

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.     

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.     

伪群作用与覆盖空间

证明了如果U是一个黎曼流形的子集,伪群G作用在它上面,若这个伪作用是第一类的,那么覆盖空间方法给出了U/G的一个正规覆盖空间;若X是一个局部紧的长度空间X,且伪群H在X的一个度量球上的作用是第二类的,则构造出来的空间是X的一个正规覆盖空间.另外,还证明了对于两类流形,存在切球上的由道路提升定义的第一类伪作用.     

关于一类几何极值问题

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

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.