On the Acyclic Chromatic Number of Hamming Graphs

An acyclic coloring of a graph G is a proper coloring of the vertex set of G such that G contains no bichromatic cycles. The acyclic chromatic number of a graph G is the minimum number k such that G has an acyclic coloring with k colors. In this paper, acyclic colorings of Hamming graphs, products of complete graphs, are considered. Upper and lower bounds on the acyclic chromatic number of Hamming graphs are given. Gretchen L. Matthews: The work of this author is supported by NSA H-98230-06-1-0008.     

联图Fn∨Pm的邻点可区别全染色

设G(V,E)是阶数至少为2的简单连通图,k是正整数,V∪E到{1,2,3,…k}的映射f满足:对任意uv,uw∈E(G),u≠w,有f(uv)≠f(vw);对任意uv∈E(G),有f(u)≠f(v), f(u)≠f(uv),f(v)≠f(uv);那么称f为G的k-正常全染色,若f还满足对任意uv∈E(G),有G(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G),v∈V(G)}那么称f为G的k-邻点可区别的全染色(简记为k-AVDTC),称min{k|G有k-邻点可区别的全染色}为G的邻点可区别的全色数,记作Xat(G)．本文得到了联图Fn∨Pm的全色数．     

Balanced Graph Partitions

We prove that the set of vertices V, |V| = rk, of a connected graph G can be split into r subsets of the same cardinality in such a way that the distance between any vertex of G and any subset of the partition is at most r.     

Coloring Vertices and Faces of Locally Planar Graphs

If G is an embedded graph, a vertex-face r-coloring is a mapping that assigns a color from the set {1, . . . ,r} to every vertex and every face of G such that different colors are assigned whenever two elements are either adjacent or incident. Let χ_vf(G) denote the minimum r such that G has a vertex-face r-coloring. Ringel conjectured that if G is planar, then χ_vf(G)≤6. A graph G drawn on a surface S is said to be 1-embedded in S if every edge crosses at most one other edge. Borodin proved that if G is 1-embedded in the plane, then χ(G)≤6. This result implies Ringel's conjecture. Ringel also stated a Heawood style theorem for 1-embedded graphs. We prove a slight strengthening of this result. If G is 1-embedded in S, let w(G) denote the edge-width of G, i.e. the length of a shortest non-contractible cycle in G. We show that if G is 1-embedded in S and w(G) is large enough, then the list chromatic number ch(G) is at most 8. Work completed while the author was the Neil R. Grabois Visiting Chair of Mathematics, Colgate University, Hamilton, NY 13346 USA. Supported in part by the Ministry of Science and Higher Education of Slovenia, Research Program P1–0507–0101.     

Linear coloring of graphs embeddable in a surface of nonnegative characteristic

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc(G) of the graph G is the smallest number of colors in a linear coloring of G. In this paper, we prove that every graph G with girth g(G) and maximum degree Δ(G) that can be embedded in a surface of nonnegative characteristic has lc(G) = Δ(2G )+ 1 if there is a pair (Δ, g) ∈ {(13, 7), (9, 8), (7, 9), (5, 10), (3, 13)} such that G s...     

The Odd-Distance Plane Graph

The vertices of the odd-distance graph are the points of the plane ℝ². Two points are connected by an edge if their Euclidean distance is an odd integer. We prove that the chromatic number of this graph is at least five. We also prove that the odd-distance graph in ℝ² is countably choosable, while such a graph in ℝ³ is not. The research of J. Maňuch was supported in part by MITACS (Mathematics of Information Technology and Complex Systems). The research of M. Rosenfeld was supported in part by the Chancellor Research Grant and the Institute of Technology, UWT. The research of S. Shelah was supported by the United States-Israel Binational Science Foundation (Grant no. 2002323), and by NSF grant No. NSF-DMS 0600940. No. 923 on Shelah’s publication list. The research of L. Stacho was supported in part by NSERC (Natural Science and Engineering Research Council of Canada) grant.     

若干倍图的均匀全染色(英文)

如果图G的一个正常全染色满足任意两种颜色所染元素(点或边)数目相差不超过1,则称为G的均匀全染色,其所用最少染色数称为均匀全色数.本文得到了星、扇和轮的倍图的均匀全色数.     

Linear coloring of planar graphs with large girth

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number of the graph G is the smallest number of colors in a linear coloring of G. In this paper we prove that every planar graph G with girth g and maximum degree Δ has if G satisfies one of the following four conditions: (1) g≥13 and Δ≥3; (2) g≥11 and Δ≥5; (3) g≥9 and Δ≥7; (4) g≥7 and Δ≥13. Moreover, we give better upper bounds of linear chromatic number for planar graphs with girth 5 or 6.     

Total colorings and list total colorings of planar graphs without intersecting 4-cycles

Suppose that G is a planar graph with maximum degree Δ and without intersecting 4-cycles, that is, no two cycles of length 4 have a common vertex. Let χ^″(G), and denote the total chromatic number, list edge chromatic number and list total chromatic number of G, respectively. In this paper, it is proved that χ^″(G)=Δ+1 if Δ≥7, and and if Δ(G)≥8. Furthermore, if G is a graph embedded in a surface of nonnegative characteristic, then our results also hold.     

不含5-圈和相邻6-圈的平面图的全染色

图的正常k-全染色是用k种颜色给图的顶点和边同时进行染色,使得相邻或者相关联的元素(顶点或边)染不同的染色.使得图G存在正常k-全染色的最小正整数k,称为图G的全色数,用χ″(G)表示.证明了若图G是最大度△≥6且不含5-圈和相邻6-圈的平面图,则χ″(G)=△+1.