The Criticality for Circular Coloring of Graph

For two positive integers k and d such that k ≥ 2d, Gkd is the graph with vertex set{0,1,…,k-1} in which ij is an edge if and only ifd ≤ |i-j|≤ k-d. Clearly, Gk1 is acomplete graph of k vertices and we always assume d ≥ 2 in the following.     

The Entire Coloring of Series-Parallel Graphs

The entire chromatic number X_(vef)(G) of a plane graph G is the minimal number of colors needed for coloring vertices, edges and faces of G such that no two adjacent or incident elements are of the same color. Let G be a series-parallel plane graph, that is, a plane graph which contains no subgraphs homeomorphic to K_(4-) It is proved in this paper that X_(vef)(G)≤max{8, △(G) 2} and X_(vef)(G)=△ 1 if G is 2-connected and △(G)≥6.     

Tverberg’s Theorem and Graph Coloring

The topological Tverberg theorem has been generalized in several directions by setting extra restrictions on the Tverberg partitions. Restricted Tverberg partitions, defined by the idea that certain points cannot be in the same part, are encoded with graphs. When two points are adjacent in the graph, they are not in the same part. If the restrictions are too harsh, then the topological Tverberg theorem fails. The colored Tverberg theorem corresponds to graphs constructed as disjoint unions of small complete graphs. Hell studied the case of paths and cycles. In graph theory these partitions are usually viewed as graph colorings. As explored by Aharoni, Haxell, Meshulam and others there are fundamental connections between several notions of graph colorings and topological combinatorics. For ordinary graph colorings it is enough to require that the number of colors q satisfy q>Δ, where Δ is the maximal degree of the graph. It was proven by the first author using equivariant topology that if q>Δ ² then the topological Tverberg theorem still works. It is conjectured that q>KΔ is also enough for some constant K, and in this paper we prove a fixed-parameter version of that conjecture. The required topological connectivity results are proven with shellability, which also strengthens some previous partial results where the topological connectivity was proven with the nerve lemma.     

The Binding Number of a Graph

The binding number of a graph is an important characteristic quantity of agraph.In1973 Woodall first introduced the concept of the binding number ofa graph and then gave the binding number of some special graphs in[1].In1981 Kane,Mohanty and Hales gave the binding number of some product graphsin[2].Wang Jianfang,Tian Songlin,Liu Ziuqiang(1983-1987)gave the bin-ding number of some multi-product graphs,and it is the limit character.Up to     

The Star-chromatic Numbers of Graph Products

Ｗｅｏｎｌｙｃｏｎｓｉｄｅｒｆｉｎｉｔｅｓｉｍｐｌｅｇｒａｐｈｓｉｎｔｈｉｓｐａｐｅｒ．Ｌｅｔｋ，ｄｂｅｎａｔｕｒａｌｎｕｍｂｅｒｓｓｕｃｈｔｈａｔｋ２ｄ，ａ（ｋ，ｄ）ｃｏｌｏｒｉｎｇｏｆａｇｒａｐｈＧ＝（Ｖ，Ｅ）ｉｓａｍａｐｐｉｎｇｃ：ＶＺｋ...     

The Graph of Binary Symmetric Matrices of Order 3

ＴｈｅＧｒａｐｈｏｆＢｉｎａｒｙＳｙｍｍｅｔｒｉｃＭａｔｒｉｃｅｓ ｏｆＯｒｄｅｒ３ｗａｎＺｈｅｘｉａｎ（万哲先）（ＩｎｓｔｉｔｕｔｅｏｆＳｙｓｔｅｍｓＳｃｉｅｎｃｅ，ＡｃａｄｅｒｍｉａＳｉｎｉｃａ，Ｂｅｉｊｉｎｇ，１０００８０）ｃｏｍｍｕｎｉｃａｔ?..     

The Domination Polynomial of a Graph at −1

Let G be a simple graph. The domination polynomial of a graph G of order n is the polynomial ${D(G,x)=\sum_{i=0}^{n} d(G,i) x^{i}}$ , where d(G, i) is the number of dominating sets of G of size i. In this article we investigate the domination polynomial at ?1. We give a construction showing that for each odd number n there is a connected graph G with D(G, ?1) = n.     

The Stationary Distribution of a Continuous-Time Random Graph Process

ＴｈｅＳｔａｔｉｏｎａｒｙＤｉｓｔｒｉｂｕｔｉｏｎｏｆａＣｏｎｔｉｎｕｏｕｓ－ＴｉｍｅＲａｎｄｏｍＧｒａｐｈＰｒｏｃｅｓｓ韩东ＴｈｅＳｔａｔｉｏｎａｒｙＤｉｓｔｒｉｂｕｔｉｏｎｏｆａＣｏｎｔｉｎｕｏｕｓ－ＴｉｍｅＲａｎｄｏｍＧｒａｐｈＰｒｏｃｅｓｓ￥...     

Equitable Coloring of Complete r-partite Graphs

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets of as near equal sizes as possible. In this paper, we determine a sufficient and necessary condition for which a complete r-partite graph is equitably k-colorable. From this result, we can provide another way to prove some previous results.     

On the Maximum Matching Graph of a Graph

1IntroductionMatchingtheory,aswellastheassignmentprobleminlinearprogramming,hasawiderangeofapplicationinthetheoryandpracticeofoperationsresearch.Bysomepracticalmotivations,e.g.,forfindingalloptimalsolutions,peoplewanttoknowthestructurepropertiesofallmaximummatchingsofagraphG.InthecasethatGhasperfectmatchings,extensiveworkhasbeendoneontheso-calledperfectmatChinggrape(or1-factorgraph),inwhichtwoperfectmatchingsMIandMZaresaidtobeadjacentifMI~MZ@E(C)whereCisanMI-alternatingcycleofG.Therewer…