图的邻点可区别全色数的一个上界

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同．本文用概率方法得到了邻点可区别全色数的一个上界．     

Upper bounds on the linear chromatic number of a graph

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is a union of vertex-disjoint paths. The linear chromatic number of G is the smallest number of colors in a linear coloring of G.Let G be a graph with maximum degree Δ(G). In this paper we prove the following results: (1) ; (2) if Δ(G)≤4; (3) if Δ(G)≤5; (4) if G is planar and Δ(G)≥52.     

On the chromatic number of a random 5‐regular graph

It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is asymptotically almost surely equal to 3, provided a certain four‐variable function has a unique maximum at a given point in a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the number of locally rainbow balanced 3‐colorings, where a coloring is balanced if the number of vertices of each color is equal, and locally rainbow if every vertex is adjacent to at least one vertex of each of the other colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 157–191, 2009     

An upper bound for the adjacent vertex distinguishing acyclic edge chromatic number of a graph

A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges incident to υ, where uυ ∈ E(G). The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by χ′ _aa (G), is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. In this paper we prove that if G(V, E) is a graph with no isolated edges, then χ′ _aa (G) ≤ 32Δ. Supported by the Natural Science Foundation of Gansu Province (3ZS051-A25-025)     

About the upper chromatic number of a co-hypergraph

A mixed hypergraph consists of two families of subsets: the edges and the co-edges. In a coloring every co-edge has at least two vertices of the same color, and every edge has at least two vertices of different colors. The largest and smallest possible number of colors in a coloring is termed the upper and lower chromatic numbers, respectively. In this paper we investigate co-hypergraphs i.e., the hypergraphs with only co-edges, with respect to the property of coloring. The relationship between the lower bound of the size of co-edges and the lower bound of the upper chromatic number is explored. The necessary and sufficient conditions for determining the upper chromatic numbers, of a co-hypergraph are provided. And the bounds of the number of co-edges of some uniform co-hypergraphs with certain upper chromatic numbers are given.     

New bounds for the chromatic number of graphs

In this article we first give an upper bound for the chromatic number of a graph in terms of its degrees. This bound generalizes and modifies the bound given in 11 . Next, we obtain an upper bound of the order of magnitude for the coloring number of a graph with small K_2,t (as subgraph), where n is the order of the graph. Finally, we give some bounds for chromatic number in terms of girth and book size. These bounds improve the best known bound, in terms of order and girth, for the chromatic number of a graph when its girth is an even integer. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:110–122, 2008     

A new upper bound for the harmonious chromatic number

A harmonious coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colors in such a coloring. We obtain a new upper bound for the harmonious chromatic number of general graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 29: 257–261, 1998     

Coloring the square of a planar graph

We prove that for any planar graph G with maximum degree Δ, it holds that the chromatic number of the square of G satisfies χ(G²) ≤ 2Δ + 25. We generalize this result to integer labelings of planar graphs involving constraints on distances one and two in the graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 110–124, 2003     

An inequality for the group chromatic number of a graph

We give an inequality for the group chromatic number of a graph as an extension of Brooks’ Theorem. Moreover, we obtain a structural theorem for graphs satisfying the equality and discuss applications of the theorem.     

Semidefinite bounds for the stability number of a graph via sums of squares of polynomials

Lovász and Schrijver (SIAM J. Optim. 1:166–190, 1991) have constructed semidefinite relaxations for the stable set polytope of a graph G = (V,E) by a sequence of lift-and-project operations; their procedure finds the stable set polytope in at most α(G) steps, where α(G) is the stability number of G. Two other hierarchies of semidefinite bounds for the stability number have been proposed by Lasserre (SIAM J. Optim. 11:796–817, 2001; Lecture Notes in Computer Science, Springer, Berlin Heidelberg New York, pp 293–303, 2001) and by de Klerk and Pasechnik (SIAM J. Optim. 12:875–892), which are based on relaxing nonnegativity of a polynomial by requiring the existence of a sum of squares decomposition. The hierarchy of Lasserre is known to converge in α(G) steps as it refines the hierarchy of Lovász and Schrijver, and de Klerk and Pasechnik conjecture that their hierarchy also finds the stability number after α(G) steps. We prove this conjecture for graphs with stability number at most 8 and we show that the hierarchy of Lasserre refines the hierarchy of de Klerk and Pasechnik.      

Hadwiger number and chromatic number for near regular degree sequences

We consider a problem related to Hadwiger's Conjecture. Let D=(d₁, d₂, …, d_n) be a graphic sequence with 0?d₁?d₂?···?d_n?n?1. Any simple graph G with D its degree sequence is called a realization of D. Let R[D] denote the set of all realizations of D. Define h(D)=max{h(G): G∈R[D]} and χ(D)=max{χ(G): G∈R[D]}, where h(G) and χ(G) are Hadwiger number and chromatic number of a graph G, respectively. Hadwiger's Conjecture implies that h(D)?χ(D). In this paper, we establish the above inequality for near regular degree sequences. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 175–183, 2010     

On the complete chromatic number of Halin graphs

ThisresearchissupportedbytheNationalNaturalScienceFoundationofChina.Write.1.IntroductionDefinition1.FOrany3-connectedplanargraphG(V,E,F)withA(G)23,iftheboundaryedgesoffacefowhichisadjacenttotheothersareremoved,itbecomesatree,andthedegreeofeachvertexofV(fo)is3,andthenGiscalledaHalingraph;foiscalledtheouterfaceofG,andtheotherscalledtheinteriorfaces,thevenicesonthefacefoarecalledtheoutervenices,theoillersarecalledtheinterior...ti..,tll.ForanyplanargraphG(V,E,F),f,f'eF,fisadjacenttof'ifan…     

On the chromatic number of random graphs

We consider random graphs G_n,p with fixed edge-probability p. We refine an argument of Bollobás to show that almost all such graphs have chromatic number equal to n/{2 log_b n ? 2 log_b log_b n + O(1)} where b = 1/(1 ? p).     

On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

Total chromatic number of planar graphs with maximum degree ten

In this article we prove that the total chromatic number of a planar graph with maximum degree 10 is 11. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 91–102, 2007     

An improved bound for the strong chromatic number

Let η > 0 be given. Then there exists d₀ = d₀(η) such that the following holds. Let G be a finite graph with maximum degree at most d ≥ d₀ whose vertex set is partitioned into classes of size α d, where α≥ 11/4 + η. Then there exists a proper coloring of G with αd colors in which each class receives all αd colors. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:148–158, 2008     

THE TOTAL CHROMATIC NUMBER OF PSEUDO-OUTERPLANAR GRAPHS

A Planar graph g is called a ipseudo outerplanar graph if there is a subset v.∈V(G),[V.]=i,such that G-V. is an outerplanar graph in particular when G-V.is a forest ,g is called a i-pseudo-tree .in this paper.the following results are proved;(1)the conjecture on the total coloring is true for all 1-pseudo-outerplanar graphs;(2)X1(G) 1 fo any 1-pseudo outerplanar graph g with △(G)≥3,where x4(G)is the total chromatic number of a graph g.     

A Graph with cover degeneracy less than chromatic number

This note contains an example of a 4‐chromatic graph which admits a vertex partition into three parts such that the union of every two of them induces a forest. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 243–246, 2001     

布尔矩阵的可实现问题及其与色数问题的关系

讨论了布尔矩阵的可实现问题及其与色数问题的关系.首先给出布尔矩阵可实现的一些充要条件,讨论可实现布尔矩阵的性质,其次证明可实现布尔矩阵的容度等于该矩阵所生成的图的色数;简单图的邻接矩阵的对偶阵是可实现的,且其容度就是简单图的色数的一个上界.