Uniform Mixed Hypergraphs: The Possible Numbers of Colors

For a mixed hypergraph , where and are set systems over the vertex set X, a coloring is a partition of X into ‘color classes’ such that every meets some class in more than one vertex, and every has a nonempty intersection with at least two classes. The feasible set of , denoted , is the set of integers k such that admits a coloring with precisely k nonempty color classes. It was proved by Jiang et al. [Graphs and Combinatorics 18 (2002), 309–318] that a set S of natural numbers is the feasible set of some mixed hypergraph if and only if either or S is an ‘interval’ for some integer k ≥ 1. In this note we consider r-uniform mixed hypergraphs, i.e. those with |C| = |D| = r for all and all , r ≥ 3. We prove that S is the feasible set of some r-uniform mixed hypergraph with at least one edge if and only if either for some natural number k ≥ r − 1, or S is of the form where S′′ is any (possibly empty) subset of and S′ is either the empty set or {r − 1} or an ‘interval’ {k, k + 1, ..., r − 1} for some k, 2 ≤ k ≤ r − 2. We also prove that all these feasible sets can be obtained under the restriction , i.e. within the class of ‘bi-hypergraphs’. Research supported in part by the Hungarian Scientific Research Fund, OTKA grant T-049613.     

Halin-图的点强全染色

图G(V,E)的一个k-正常全染色f叫做一个k-点强全染色当且仅当对任意v∈V(G), N[v]中的元素被染不同色,其中N[v]={u|uv∈V(G)}∪{v}．χTvs(G)=min{k|存在图G的k- 点强全染色}叫做图G的点强全色数．对3-连通平面图G(V,E),如果删去面fo边界上的所有点后的图为一个树图,则G(V,E)叫做一个Halin-图．本文确定了最大度不小于6的Halin- 图和一些特殊图的的点强全色数XTvs(G),并提出了如下猜想:设G(V,E)为每一连通分支的阶不小于6的图,则χTvs(G)≤△(G) 2,其中△(G)为图G(V,E)的最大度．     

基于颜色传递和目标增强的夜视图像彩色融合

颜色传递是获得夜视图像自然彩色的一种方法,以红外和微光图像为研究对象,提出了一种基于颜色传递和目标增强的夜视图像彩色融合方法。首先结合红外和微光图像各自的特点,采用TNO法生成伪彩色融合图像(目标图像),很好地保留了图像的细节信息,然后选取一幅相近的参考图像,把目标图像和参考图像转换到YCbCr颜色空间进行各个通道一阶(均值)和二阶(标准差)统计量匹配的颜色传递,同时在Cr通道引入一个对比度增强因子来增强图像中的兴趣目标。实验结果表明,文中方法不仅使得夜视图像获得了如白天参考图像般自然、真实的色彩,而且提高了图像的细节,目标也更加突出,更有利于观察者对场景的理解。     

大规模MIMO系统中基于图着色的半动态导频分配

针对大规模MIMO系统中存在的导频污染问题,提出了一种基于图着色的半动态导频分配方案。首先,推导出各个小区可以复用导频的用户与其服务基站的最大距离门限。然后,根据该门限值将系统内各小区的用户分为小区中心用户和小区边缘用户;允许各个小区门限值之内的用户（小区中心用户）复用相同的导频;最后,基于图着色理论协同分配各个小区的小区边缘用户的导频,达到降低导频干扰的目的。仿真结果显示,该方案减少了用户间的导频干扰,有效地提升了整个系统的上行可达和速率。     

完全图的广义Mycielski图的邻强边染色

对|V(G)|≥3的连通图G,若κ-正常边染色法满足相邻点的色集合不相同,则称该染色法为κ-邻强边染色,其最小的κ称为图G的邻强边色数。张忠辅等学者猜想:对|V(G)|≥3的连通图G,G≠C_5其邻强边色数至多为△(G)+2,利用组合分析的方法给出了完全图的广义Mycielski图的邻强边色数,从而验证了图的邻强边染色猜想对于此类图成立。     

酒类中微量甲醛的快速测定新方法

在FeCl3存在条件下,甲醛与自制蛋白液显色剂能生成紫色化合物,藉此可以定量测定微量甲醛。方法线性范围为1~10μg/10mL,线性相关系数r2=0.996,检出限为0.05μg/mL。用该法测定经活性炭脱色的啤酒和白酒中的甲醛含量,回收率为96.46%~103.32%,相对标准偏差为1.36%~2.09%(n=6)。     

An improved approximation algorithm for requirement cut

This note presents improved approximation guarantees for the requirement cut problem: given an n-vertex edge-weighted graph G=(V,E), and g groups of vertices X₁,…,X_g⊆V with each group X_i having a requirement r_i between 0 and |X_i|, the goal is to find a minimum cost set of edges whose removal separates each group X_i into at least r_i disconnected components. We give a tight Θ(logg) approximation ratio for this problem when the underlying graph is a tree, and show how this implies an O(logk⋅logg) approximation ratio for general graphs, where .     

Plane Graphs with Maximum Degree Are Entirely ‐Colorable

Let be a plane graph with the sets of vertices, edges, and faces V, E, and F, respectively. If one can color all elements in using k colors so that any two adjacent or incident elements receive distinct colors, then G is said to be entirely k‐colorable. Kronk and Mitchem [Discrete Math 5 (1973) 253‐260] conjectured that every plane graph with maximum degree Δ is entirely ‐colorable. This conjecture has now been settled in Wang and Zhu (J Combin Theory Ser B 101 (2011) 490–501), where the authors asked: is every simple plane graph entirely ‐colorable? In this article, we prove that every simple plane graph with is entirely ‐colorable, and conjecture that every simple plane graph, except the tetrahedron, is entirely ‐colorable.     

Interference coordination method based on graph theory in two-tier cellular networks

This paper studies an interference coordination method by means of spectrum allocation in Long-Term Evolution (LTE) multi-cell scenario that comprises of macrocells and femtocells. The purpose is to maximize the total throughput of femtocells while ensuring the Signal-to-Interference plus Noise Ratio (SINR) of the edge macro mobile stations (mMSs) and the edge femtocell Mobile Stations (fMSs). A new spectrum allocation algorithm based on graph theory is proposed to reduce the interference. Firstly, the ratio of Resource Blocks (RBs) that mMSs occupy is obtained by genetic algorithm. Then, after considering the impact of the macro Base Stations (mBSs) and small scale fading to the fMS on different RBs, multi-interference graphs are established and the spectrum is allocated dynamically. The simulation results show that the proposed algorithm can meet the Quality of Service (QoS) requirements of the mMSs. It can strike a balance between the edge fMSs’ throughput and the whole fMSs’ throughput.