若干联图的均匀全染色

图$G(V,E)$的全色数 $\chi_{t}(G)$就是将$V\bigcup E$分成彼此不相交的全独立分割集的最小个数。 如果任何两个$V\bigcup E$的全独立分割集的元素数目相差不超过1，那么 $V \bigcup E$的全独立分割集的最小个数就称为图$G$的均匀全色数，记为$\chi_{et}(G)$。 在本文中我们给出了当 $m \geq n \geq 3$ 时 $W_m\bigvee K_n$，$F_m \bigvee K_n$及$S_m \bigvee K_n$ 的均匀全色数.     

An Efficient Branch-and-bound Algorithm for Finding a Maximum Clique with Computational Experiments

We present an exact and efficient branch-and-bound algorithm MCR for finding a maximum clique in an arbitrary graph. The algorithm is not specialized for any particular type of graph. It employs approximate coloring to obtain an upper bound on the size of a maximum clique along with an improved appropriate sorting of vertices. We demonstrate by computational experiments on random graphs with up to 15,000 vertices and on DIMACS benchmark graphs that in general, our algorithm decidedly outperforms other existing algorithms. The algorithm has been successfully applied to interesting problems in bioinformatics, image processing, design of quantum circuits, and design of DNA and RNA sequences for biomolecular computation.     

Another look at graph coloring via propositional satisfiability

This paper studies the solution of graph coloring problems by encoding into propositional satisfiability problems. The study covers three kinds of satisfiability solvers, based on postorder reasoning (e.g., grasp, chaff), preorder reasoning (e.g., 2cl, 2clsEq), and back-chaining (modoc). The study evaluates three encodings, one of them believed to be new. Some new symmetry-breaking methods, specific to coloring, are used to reduce the redundancy of solutions. A by-product of this research is an implemented lower-bound technique that has shown improved lower bounds for the chromatic numbers of the long-standing unsolved random graphs known as DSJC125.5 and DSJC125.9. Independent-set analysis shows that the chromatic numbers of DSJC125.5 and DSJC125.9 are at least 18 and 40, respectively, but satisfiability encoding was able to demonstrate only that the chromatic numbers are at least 13 and 38, respectively, within available time and space.     

A simple criterion on degree sequences of graphs

A finite sequence of nonnegative integers is called graphic if the terms in the sequence can be realized as the degrees of vertices of a finite simple graph. We present two new characterizations of graphic sequences. The first of these is similar to a result of Havel-Hakimi, and the second equivalent to a result of Erd?s & Gallai, thus providing a short proof of the latter result. We also show how some known results concerning degree sets and degree sequences follow from our results.     

Simulation Study for the Clan of Ancestors in a Perfect Simulation Scheme of a Continuous One-Dimensional Loss Network

Perfect simulation of a one-dimensional loss network on ℝ with length distribution π and cable capacity C is performed using the clan of ancestors method. Previous works estimated the region of convergence of this scheme using a domination by a branching process. In this work, we show that the domination by the branching process is far from sharp and that there is room for improvement. Moreover, we derive an empirical relation concerning the critical value using simulation studies on the number of rectangles present in the clan of ancestors.      

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 Δ(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) Δ(H)?1 if g(G)?11; (2) Δ(H)?2 if g(G)?7; (3) Δ(H)?4 if either g(G)?5 or G does not contain 4-cycles and 5-cycles; (4) Δ(H)?6 if G does not contain 4-cycles. These results are applied to find the following upper bounds for the game coloring number col_g(G) of G: (1) col_g(G)?5 if g(G)?11; (2) col_g(G)?6 if g(G)?7; (3) col_g(G)?8 if either g(G)?5 or G contains no 4-cycles and 5-cycles; (4) col_g(G)?10 if G does not contain 4-cycles.     

Odd Perfect Numbers: Some New Issues

Periodica Mathematica Hungarica -     

On vertex-coloring 13-edge-weighting

L. Addario-Berry et al. [Discrete Appl. Math., 2008, 156: 1168-1174] have shown that there exists a 16-edge-weighting such that the induced vertex coloring is proper. In this note, we improve their result and prove that there exists a 13-edge-weighting of a graph G, such that its induced vertex coloring of G is proper. This result is one step close to the original conjecture posed by M. Karoński et al.      

Clique‐coloring some classes of odd‐hole‐free graphs

We consider the problem of clique‐coloring, that is coloring the vertices of a given graph such that no maximal clique of size at least 2 is monocolored. Whereas we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, the existence of a constant C such that any perfect graph is C‐clique‐colorable is an open problem. In this paper we solve this problem for some subclasses of odd‐hole‐free graphs: those that are diamond‐free and those that are bull‐free. We also prove the NP‐completeness of 2‐clique‐coloring K₄‐free perfect graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 233–249, 2006     

On f-edge Cover Chromatic Index of Multigraphs

Let G be a multigraph with vertex set V（G）. Assume that a positive integer f（v） with 1 ≤ f（v） ≤ d（v） is associated with each vertex v ∈ V. An edge coloring of G is called an f-edge cover-coloring, if each color appears at each vertex v at least f（v） times. Let X＇fc（G） be the maximum positive integer k for which an f-edge cover-coloring with k colors of G exists. In this paper, we give a new lower bound of X＇fc（G）, which is sharp.