Uniquely Tree Colorable Graphs

In this paper, the concepts of tree chromatic numbers and uniquely tree colorable graphs are introduced. After discussion some fundamental properties, three necessary conditions for a simple graph to be uniquely tree colorable are given. Moreover, a series of uniquely tree colorable graphs are constructed.

New mixed broadcast scheduling approach using neural networks and graph coloring in wireless sensor network

Due to the mutual interference and sharing of wireless links in TDMA wireless sensor networks, conflicts will occur when data messages are transmitting between nodes. The broadcast scheduling problem （BSP） is aimed to schedule each node in different slot of fixed length frame at least once, and the objective of BSP is to seek for the optimal feasible solution, which has the shortest length of frame slots, as well as the maximum node transmission. A two-stage mixed algorithm based on a fuzzy Hopfield neural network is proposed to solve this BSP in wireless sensor network. In the first stage, a modified sequential vertex coloring algorithm is adopted to obtain a minimal TDMA frame length. In the second stage, the fuzzy Hopfleld network is utilized to maximize the channel utilization ratio. Experimental results, obtained from the running on three benchmark graphs, show that the algorithm can achieve better performance with shorter frame length and higher channel utilizing ratio than other exiting BSP solutions.

Network evolution driven by dynamics applied to graph coloring

An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other hand, the dynamics of the network are determined by the topology and the coupling weights, so an interesting structure-dynamics co-evolutionary scheme appears. By providing two evolutionary strategies, a network described by the complement of a graph will evolve into several clusters of nodes according to their dynamics. The nodes in each cluster can be assigned the same color and nodes in different clusters assigned different colors. In this way, a co-evolution phenomenon is applied to the graph coloring problem. The proposed scheme is tested on several benchmark graphs for graph coloring.

An Intelligent Prediction Model for Target Protein Identification in Hepatic Carcinoma Using Novel Graph Theory and ANN Model

Hepatocellular carcinoma(HCC)is one major cause of cancer-related mortality around the world.However,at advanced stages of HCC,systematic treatment options are currently limited.As a result,new pharmacological targetsmust be discovered regularly,and then tailored medicines against HCC must be developed.In this research,we used biomarkers of HCC to collect the protein interaction network related to HCC.Initially,DC(Degree Centrality)was employed to assess the importance of each protein.Then an improved Graph Coloring algorithm was used to rank the target proteins according to the interaction with the primary target protein after assessing the top ranked proteins related to HCC.Finally,physio-chemical proteins are used to evaluate the outcome of the top ranked proteins.The proposed graph theory and machine learning techniques have been compared with six existing methods.In the proposed approach,16 proteins have been identified as potential therapeutic drug targets for Hepatic Carcinoma.It is observable that the proposed method gives remarkable performance than the existing centrality measures in terms of Accuracy,Precision,Recall,Sensitivity,Specificity and F-measure.

On the Maximum Number of Dominating Classes in Graph Coloring

We investigate the dominating-c-color number,, of a graph G. That is the maximum number of color classes that are also dominating when G is colored using colors. We show that where is the join of G and . This result allows us to construct classes of graphs such that and thus provide some information regarding two questions raised in [1] and [2].

A novel nest-based scheduling method for mobile wireless body area networks

Wireless Body Area Networks(WBANs)comprise various sensors to monitor and collect various vital signals,such as blood pressure,pulse,heartbeat,body temperature,and blood sugar.A dense and mobile WBAN often suffers from interference,which causes serious problems,such as wasting energy and degrading throughput.In reality,not all of the sensors in WBAN need to be active at the same time.Therefore,they can be divided into different groups so that each group works in turn to avoid interference.In this paper,a Nest-Based WBAN Scheduling(NBWS)algorithm is proposed to cluster sensors of the same types in a single or multiple WBANs into different groups to avoid interference.Particularly,we borrow the graph coloring theory to schedule all groups to work using a Time Division for Multimodal Sensor(TDMS)group scheduling model.Both theoretical analysis and experimental results demonstrate that the proposed NBWS algorithm performs better in terms of frequency of collisions,transmission delay,system throughput,and energy consumption compared to the counterpart methods.

Independent Cycle Time Assignment for Min-max Systems

A variety of problems in digital circuits, computer networks, automated manufacturing plants, etc., can be modeled as min-max systems. The cycle time is an important performance metric of such systems. In this paper, we focus on the cycle time assignment of minimax systems which corresponds to the pole assignment problem in traditional linear control systems. For the min- max system with max-plus inputs and outputs, we show that the cycle time can be assigned disjointedly by a state feedback, if and only if the system is reachable. Furthermore, a necessary and sufficient condition for the cycle time to be assigned independently by a state feedback is given. The methods are constructive, and some numerical examples are given to illustrate how the methods work in practice.

Application of CorelDRAW in Environmental Art Design

CorelDRAW has particular uses in architectural design, interior design and landscape design. By comparing several software, it was found that CorelDRAW had the working plan drawing of AutoCAD, mapping of 3DMAX, and better typesetting than Photoshop had, thus it plays an irreplaceable role in drawing working plan of environmental art design, especially colored plane and elevation view drawings.

Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling

This paper investigates the robust graph coloring problem with application to a kind of examination timetabling by using the matrix semi-tensor product, and presents a number of new results and algorithms. First, using the matrix semi-tensor product, the robust graph coloring is expressed into a kind of optimization problem taking in an algebraic form of matrices, based on which an algorithm is designed to find all the most robust coloring schemes for any simple graph. Second, an equivalent problem of robust graph coloring is studied, and a necessary and sufficient condition is proposed, from which a new algorithm to find all the most robust coloring schemes is established. Third, a kind of examination timetabling is discussed by using the obtained results, and a method to design a practicable timetabling scheme is presented. Finally, the effectiveness of the results/algorithms presented in this paper is shown by two illustrative examples.

SRF Coloring:Stream Register File Allocation via Graph Coloring

Stream Register File （SRF） is a large on-chip memory of the stream processor and its efficient management is essential for good performance. Current stream programming languages expose the management of SRF to the programmer, incurring heavy burden on the programmer and bringing difficulties to inheriting the legacy codes. SF95 is the language developed for FT64 which is the first 64-bit stream processor designed for scientific applications. SF95 conceals SRF from the programmer and leaves the management of SRF to its compiler. In this paper, we present a compiler approach named SRF Coloring to manage SRF automatically. The novelties of this paper are： first, it is the first time to use the graph coloring-based algorithm for the SRF management; second, an algorithm framework for SRF Coloring that is well suited to the FT64 architecture is proposed this framework is based on a well-understood graph coloring algorithm for register allocation, together with some modifications to deal with the unusual aspects of SRF problem; third, the SRF Coloring algorithm is implemented in SF95Compiler, a compiler designed for FT64 and SF95. The experimental results show that our approach represents a practical and promising solution to SRF allocation.

Acyclic colorings of graphs with bounded degree

A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5 coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2 coloring in which each color class induces a graph with maximum degree at most 3 is NP complete, even for graphs with maximum degree 5. We also give a linear time algorithm for an acyclic t improper coloring of any graph with maximum degree d assuming that the number of colors is large enough.

Edge choosability of planar graphs without short cycles

In this paper we prove that if G is a planar graph with △= 5 and without 4-cycles or 6-cycles, then G is edge-6-choosable. This consequence together with known results show that, for each fixed k ∈{3,4,5,6}, a k-cycle-free planar graph G is edge-(△+ 1)-choosable, where △ denotes the maximum degree of G.

Compact n-Manifolds via(n+l)-Colored Graphs:a New Approach

We introduce a representation via(n+l)-colored graphs of compact n-manifolds with(possibly empty)boundary,which appears to be very convenient for computer aided study and tabulation.Our construction is a generalization to arbitrary dimension of the one recently given by Cristofori and Mulazzani in dimension three,and it is dual to the one given by Pezzana in the 1970s.In this context we establish some results concerning the topology of the represented manifolds:suspensions,fundamental groups,connected sums and moves between graphs representing the same manifold.Classification results of compact orientable 4-manifolds representable by graphs up to six vertices are obtained,together with some properties of the G-degree of 5-colored graphs relating this approach to tensor models theory.

VColor^(*):a practical approach for coloring large graphs

Graph coloring has a wide range of real world applications,such as in the operations research,communication network,computational biology and compiler optimization fields.In our recent work[1],we propose a divide-andconquer approach for graph coloring,called VColor.Such an approach has three generic subroutines.(i)Graph partition subroutine:VColor partitions a graph G into a vertex cut partition(VP),which comprises a vertex cut component(VCC)and small non-overlapping connected components(CCs).(ii)Component coloring subroutine:VColor colors the VCC and the CCs by efficient algorithms.(iii)Color combination subroutine:VColor combines the local colors by exploiting the maximum matchings of color combination bigraphs(CCBs).VColor has revealed some major bottlenecks of efficiency in these subroutines.Therefore,in this paper,we propose VColor^(*),an approach which addresses these efficiency bottlenecks without using more colors both theoretically and experimentally.The technical novelties of this paper are the following.(i)We propose the augmented VP to index the crossing edges of the VCC and the CCs and propose an optimized CCB construction algorithm.(ii)For sparse CCs,we propose using a greedy coloring algorithm that is of polynomial time complexity in the worst case,while preserving the approximation ratio.(iii)We propose a distributed graph coloring algorithm.Our extensive experimental evaluation on real-world graphs confirms the efficiency of VColor^(*).In particular,VColor^(*)is 20X and 50X faster than VColor and uses the same number of colors with VColor on the Pokec and PA datasets,respectively.VColor^(*)also significantly outperforms the state-ofthe-art graph coloring methods.

Rainbow and Monochromatic Vertex-connection of Random Graphs

A vertex-colored path P is rainbow if its internal vertices have distinct colors;whereas P is monochromatic if its internal vertices are colored the same.For a vertex-colored connected graph G,the rainbow vertex-connection number rvc(G)is the minimum number of colors used such that there is a rainbow path joining any two vertices of G;whereas the monochromatic vertex-connection number mvc(G)is the maximum number of colors used such that any two vertices of G are connected by a monochromatic path.These two opposite concepts are the vertex-versions of rainbow connection number rc(G)and monochromatic connection number mc(G)respectively.The study on rc(G)and mc(G)of random graphs drew much attention,and there are few results on the rainbow and monochromatic vertex-connection numbers.In this paper,we consider these two vertex-connection numbers of random graphs and establish sharp threshold functions for them,respectively.

A Note on List Edge and List Total Coloring of Planar Graphs without Adjacent Short Cycles

LetGbe a planar graph with maximum degreeΔ.In this paper,we prove that if any4-cycle is not adjacent to ani-cycle for anyi∈{3,4}in G,then the list edge chromatic numberχl（G）=Δand the list total chromatic numberχl（G）=Δ＋1.

基于图着色理论的多飞艇多载荷协同对地观测和数据传输调度模型与算法

临近空间平台是一类新兴的空间平台,可用于局部区域的对地观测.本文针对飞艇的特性和用户需求的复杂性,设计了多飞艇多载荷协同对地观测和数据传输体系,考虑常规观测任务的调度,以及应急观测任务的重调度.基于图着色理论(graph coloring theory,GCT),构建多飞艇多载荷协同对地观测和数据传输调度模型.将多飞艇协同对地观测与数据传输任务、任务间的冲突、以及飞艇和地面站分别映射为无向图中的点、边和颜色,从而将问题构建为图着色问题(graph coloring problem,GCP),最大化完成任务总收益的优化目标转换为GCP中最大化着色点收益.提出一种文化基因算法(memetic algorithm,MA),设计基于收益改进的禁忌搜索(Tabu search,TS)算子更新染色体,和对父代染色体中最大收益的连续基因进行遗传的交叉策略.数值实验结果表明,针对不同规模的算例,相较于TS和ILOG CPLEX,MA能够在合理时间内获得更满意的解.

Managing Data-Objects in Dynamically Reconfigurable Caches

The widening gap between processor and memory speeds makes cache an important issue in the computer system design. Compared with work set of programs, cache resource is often rare. Therefore, it is very important for a computer system to use cache efficiently. Toward a dynamically reconfigurable cache proposed recently, DOOC （Data- Object Oriented Cache）, this paper proposes a quantitative framework for analyzing the cache requirement of data-objects, which includes cache capacity, block size, associativity and coherence protocol. And a kind of graph coloring algorithm dealing with the competition between data-objects in the DOOC is proposed as well. Finally, we apply our approaches to the compiler management of DOOC. We test our approaches on both a single-core platform and a four-core platform. Compared with the traditional caches, the DOOC in both platforms achieves an average reduction of 44.98% and 49.69% in miss rate respectively. And its performance is very close to the ideal optimal cache.

Novel scheme for interference avoidance in cognitive radio based cellular networks

The cognitive radio （CR） technology is believed to improve the spectrum efficiency. However, the interference problem has become a critical issue due to the coexistence of primary systems and CR systems. In this paper, the interferences in CR based cellular networks are discussed. Interference scenarios are analyzed, considering different interference sources. Meanwhile, an improved model named ＇Cognitive Interference Ring＇ is introduced to describe the interference range of each secondary user （SU）. Depending on the above analysis, graph coloring based dynamic power allocation （GCDPA） scheme is proposed for interference avoidance. Simulation results demonstrate that in CR based cellular networks, the interferences to primary users （PUs） can be effectively mitigated with the proposed GCDPA scheme, and the system throughput and power efficiency are both improved.

Improved Upper Bounds on Acyclic Edge Colorings

An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors. The acyclic chromatic index of a graph G, denoted by a＇（G）, is the minimum number k such that there is an acyclic edge coloring using k colors. It is known that a＇（G） ≤ 16△ for every graph G where △denotes the maximum degree of G. We prove that a＇（G） 〈 13.8A for an arbitrary graph G. We also reduce the upper bounds of a＇（G） to 9.8△ and 9△ with girth 5 and 7, respectively.