41218825
Relaxed game chromatic number of graphs
This paper discusses a coloring game on graphs. Let k, d be non-negative integers and C a set of k colors. Two persons, Alice and Bob, alternately color the vertices of G with colors from C, with Alice having the first move. A color i is legal for an uncolored vertex x if by coloring x with color i, the subgraph of G induced by those vertices of color i has maximum degree at most d. Each move of Alice or Bob colors an uncolored vertex with a legal color. The game is over if either all vertices are colored, or no more vertices can be colored with a legal color. Alice's goal is to produce a legal coloring which colors all the vertices of G, and Bob's goal is to prevent this from happening. We shall prove that if G is a forest, then for k = 3, d ≥ 1, Alice has a winning strategy. If G is an outerplanar graph, then for k = 6 and d ≥ 1, Alice has a winning strategy.
13354529
Edge-pancyclicity of coupled graphs
The coupled graph c(G) of a plane graph G is the graph defined on the vertex set V(G)∪F(G) so that two vertices in c(G) are joined by an edge if and only if they are adjacent or incident in G. We prove that the coupled graph of a 2-connected plane graph is edge-pancyclic. However, there exists a 2-edge-connected plane graph G such that c(G) is not Hamiltonian.
11186519
Edge-partitions of graphs of nonnegative characteristic and their game coloring numbers
Let G be a graph of nonnegative characteristic and let g(G) and @D(G) be its girth and maximum degree, respectively. We show that G has an edge-partition into a forest and a subgraph H so that (1) @D(H)= =11; (2) @D(H)= =7; (3) @D(H)= =5 or G does not contain 4-cycles and 5-cycles; (4) @D(H)= =11; (2) col"g(G)= =7; (3) col"g(G)= =5 or G contains no 4-cycles and 5-cycles; (4) col"g(G)=<10 if G does not contain 4-cycles.
26709203
The Linear 2-Arboricity of Outerplanar Graphs
6853966
Total chromatic number of planar graphs with maximum degree ten
1003852
Upper Bounds of Entire Chromatic Number of Plane Graphs
The entire chromatic number χvef (G) of a plane graph G is the least number of colors assigned to the vertices, edges and faces so that every two adjacent or incident pair of them receive different colors. Kronk and Mitchem (1973) conjectured that χvef (G) ≤ 1 + 4 for every plane graph G. In this paper we prove the conjecture for a plane graph G having χ ′(G) = 1 and give a upper bound χvef (G) ≤ 1+ 5 for all plane graphs, where χ ′(G) and 1 are the chromatic index and the maximum degree of G, respectively.
29035045
Genetic algorithms for determining fuzzy measures from data
A synthetic evaluation of a given object in terms of multiple factors that contribute to some feature of the object (quality, performance, etc.) may be regarded as a system with multiple inputs and one output. Traditionally, the output is expressed as the weighted average of the inputs. Unfortunately, this method is severely limited as it cannot capture any inherent relation among the factors involved. This limitation can be overcome by using the Choquet integral or the fuzzy integral with respect to a fuzzy measure that captures the relation among the factors. The crux of this method is to determine the right fuzzy measure. In this paper, we describe an efficient genetic algorithm for constructing a suitable fuzzy measure from relevant input-output data. This algorithm has a broad applicability in various problem areas, such as decision making, cluster analysis, pattern recognition, image and speech processing, and expert systems.
11138955
Computing an Almost Minimum Set of Spanning Line Segments of a Polyhedron
A set of spanning line segments (SLS) is a subset of the edges of a finite polyhedron in E3 such that an arbitrary plane intersects the polyhedron if and only if the plane intersects at least one of the line segments of the SLS. In this paper an algorithm is presented for computing an almost minimum set of spanning line segments for an arbitrary polyhedron . When the number of extreme vertices of is odd, the computed SLS is minimum; when the number of extreme vertices of is even, the size of the computed SLS is at most the minimum size plus one. The algorithm has linear-time complexity for a convex polyhedron, hence is optimal in this case; its time complexity is Θ(m log m) for an arbitrary polyhedron, where m is the number of vertices of the polyhedron.
1166455
Comparing Graph Representations of Protein Structure for Mining Family-Specific Residue-Based Packing Motifs
We find recurring amino-acid residue packing patterns, or spatial motifs, that are characteristic of protein structural families, by applying a novel frequent subgraph mining algorithm to graph representations of protein three-dimensional structure. Graph nodes represent amino acids, and edges are chosen in one of three ways: first, using a threshold for contact distance between residues; second, using Delaunay tessellation; and third, using the recently developed almost-Delaunay edges. For a set of graphs representing a protein family from the Structural Classification of Proteins (SCOP) database, subgraph mining typically identifies several hundred common subgraphs corresponding to spatial motifs that are frequently found in proteins in the family but rarely found outside of it. We find that some of the large motifs map onto known functional regions in two protein families explored in this study, i.e., serine proteases and kinases. We find that graphs based on almost-Delaunay edges significantly reduce the number of edges in the graph representation and hence present computational advantage, yet the patterns extracted from such graphs have a biological interpretation approximately equivalent to that of those extracted from distance based graphs.
10774024
Accurate Classification of Protein Structural Families Using Coherent Subgraph Analysis
Protein structural annotation and classification is an important problem in bioinformatics. We report on the development of an efficient subgraph mining technique and its application to finding characteristic substructural patterns within protein structural families. In our method, protein structures are represented by graphs where the nodes are residues and the edges connect residues found within certain distance from each other. Application of subgraph mining to proteins is challenging for a number reasons: (1) protein graphs are large and complex, (2) current protein databases are large and continue to grow rapidly, and (3) only a small fraction of the frequent subgraphs among the huge pool of all possible subgraphs could be significant in the context of protein classification. To address these challenges, we have developed an information theoretic model called coherent subgraph mining. From information theory, the entropy of a random variable X measures the information content carried by X and the Mutual Information (MI) between two random variables X and Y measures the correlation between X and Y. We define a subgraph X as coherent if it is strongly correlated with every sufficiently large sub-subgraph Y embedded in it. Based on the MI metric, we have designed a search scheme that only reports coherent subgraphs. To determine the significance of coherent protein subgraphs, we have conducted an experimental study in which all coherent subgraphs were identified in several protein structural families annotated in the SCOP database (Murzin et al, 1995). The Support Vector Machine algorithm was used to classify proteins from different families under the binary classification scheme. We find that this approach identifies spatial motifs unique to individual SCOP families and affords excellent discrimination between families.
2396831
Mining coherent patterns from heterogeneous microarray data
Microarray technology is a powerful tool for geneticists to monitor interactions among tens of thousands of genes simultaneously. There has been extensive research on coherent subspace clustering of gene expressions measured under consistent experimental settings. However, these methods assume that all experiments are run using the same batch of microarray chips with similar characteristics of noise. Algorithms developed under this assumption may not be applicable for analyzing data collected from heterogeneous settings, where the set of genes being monitored may be different and expression levels may be not directly comparable even for the same gene. In this paper, we propose a model, F-cluster, for mining subspace coherent patterns from heterogeneous gene expression data. We compare our model with previously proposed models. We analyze the search space of the problem and give a naïve solution for it.