一类4-正则平面图的邻点可区别关联色数

所谓图R_n是指具有如下结构的平面图:R_n=(V,E),其中顶点集合V={u_1,u_2,…,u_n}U{v_1,v_2,…,v_n},边集合E={u_iu_(i+1),v_iv_(i+1),u_iv_i,u_iv_(i+1)|i=1,2,…,n},其中u_(n+1)=u_1,v_(n+1)=v_1.通过研究R_n的邻点可区别关联着色,给出了当n=4,n是3或者5的正整数倍时,R_n的邻点可区别关联色数.     

On some colorings of a double graph

In this note, we present some results concerning the chromatic index, the total chromatic index, the adjacent vertex distinguishing chromatic index and the adjacent vertex distinguishing total chromatic index for double graphs. In particular, we study the double graphs of class 1 and of type 1.     

高度平面图的邻点可区别全染色

图G 的邻点可区别全染色是G 的一个正常全染色, 使得每一对相邻顶点有不同的颜色集合. G的邻点可区别全色数χ_a′′ (G) 是使得G 有一个k- 邻点可区别全染色的最小颜色数k. 本文证明了: 若G 是满足最大度Δ(G) ≥ 11 的平面图, 则χ_a′′ (G) ≤ Δ(G) + 3.     

Planar graph colorings without short monochromatic cycles

It is well known that every planar graph G is 2‐colorable in such a way that no 3‐cycle of G is monochromatic. In this paper, we prove that G has a 2‐coloring such that no cycle of length 3 or 4 is monochromatic. The complete graph K₅ does not admit such a coloring. On the other hand, we extend the result to K₅‐minor‐free graphs. There are planar graphs with the property that each of their 2‐colorings has a monochromatic cycle of length 3, 4, or 5. In this sense, our result is best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 25–38, 2004     

3‐Coloring Triangle‐Free Planar Graphs with a Precolored 8‐Cycle

Let G be a planar triangle‐free graph and let C be a cycle in G of length at most 8. We characterize all situations where a 3‐coloring of C does not extend to a proper 3‐coloring of the whole graph.     

Variable space search for graph coloring

Let G=(V,E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1,…,k}) to each vertex of G so that no edge has both endpoints with the same color. We propose a new local search methodology, called Variable Space Search, which we apply to the k-coloring problem. The main idea is to consider several search spaces, with various neighborhoods and objective functions, and to move from one to another when the search is blocked at a local optimum in a given search space. The k-coloring problem is thus solved by combining different formulations of the problem which are not equivalent, in the sense that some constraints are possibly relaxed in one search space and always satisfied in another. We show that the proposed algorithm improves on every local search used independently (i.e., with a unique search space), and is competitive with the currently best coloring methods, which are complex hybrid evolutionary algorithms.     

The random planar graph process

We consider the following variant of the classical random graph process introduced by Erd?s and Rényi. Starting with an empty graph on n vertices, choose the next edge uniformly at random among all edges not yet considered, but only insert it if the graph remains planar. We show that for all ε > 0, with high probability, θ(n²) edges have to be tested before the number of edges in the graph reaches (1 + ε)n. At this point, the graph is connected with high probability and contains a linear number of induced copies of any fixed connected planar graph, the first property being in contrast and the second one in accordance with the uniform random planar graph model. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

The number of defective colorings of graphs on surfaces

A (k, 1)‐coloring of a graph is a vertex‐coloring with k colors such that each vertex is permitted at most 1 neighbor of the same color. We show that every planar graph has at least cρⁿ distinct (4, 1)‐colorings, where c is constant and ρ≈1.466 satisfies ρ³ = ρ² + 1. On the other hand for any ε>0, we give examples of planar graphs with fewer than c(? + ε)ⁿ distinct (4, 1)‐colorings, where c is constant and . Let γ(S) denote the chromatic number of a surface S. For every surface S except the sphere, we show that there exists a constant c′ = c′(S)>0 such that every graph embeddable in S has at least c′2ⁿ distinct (γ(S), 1)‐colorings. © 2010 Wiley Periodicals, Inc. J Graph Theory 28:129‐136, 2011     

Upper bounds on vertex distinguishing chromatic index of some Halin graphs

A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph G is denoted by ???? _s (G). In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with ??(G) ?? 4, respectively.     

The competition number of a graph and the dimension of its hole space

The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between x and y if and only if there exists a vertex v in D such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of the important research problems in the study of competition graphs to characterize a graph by its competition number. Recently, the relationship between the competition number and the number of holes of a graph has been studied. A hole of a graph is a cycle of length at least 4 as an induced subgraph. In this paper, we conjecture that the dimension of the hole space of a graph is not smaller than the competition number of the graph. We verify this conjecture for various kinds of graphs and show that our conjectured inequality is indeed an equality for connected triangle-free graphs.     

The odd-valued chromatic polynomial of a signed graph

For a signed graph $\mathrm{\Sigma }=(G,\sigma )$, Zaslavsky defined a proper coloring on Σ and showed that the function counting the number of such colorings is a quasi-polynomial with period two, that is, a pair of polynomials, one for odd values and the other for even values. In this paper, we focus on the case of odd, written as $\chi (\mathrm{\Sigma },x)$ for short. We initially give a homomorphism expression of such colorings, by which the symmetry is considered in counting the number of homomorphisms. Besides, the explicit formulas $\chi (\mathrm{\Sigma },x)$ for some basic classes of signed graphs are presented. As a main result, we give a combinatorial interpretation of the coefficients in $\chi (\mathrm{\Sigma },x)$ and present several applications. In particular, the constant term in $\chi (\mathrm{\Sigma },x)$ gives a new criterion for balancing and a characterization for unbalanced unicyclic graph. At last, we also give a tight bound for the constant term of $\chi (\mathrm{\Sigma },x)$.     

(2 + ϵ)‐Coloring of planar graphs with large odd‐girth

The odd‐girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function ƒ(ϵ) for each ϵ : 0 < ϵ < 1 such that, if the odd‐girth of a planar graph G is at least ƒ(ϵ), then G is (2 + ϵ)‐colorable. Note that the function ƒ(ϵ) is independent of the graph G and ϵ → 0 if and only if ƒ(ϵ) → ∞. A key lemma, called the folding lemma, is proved that provides a reduction method, which maintains the odd‐girth of planar graphs. This lemma is expected to have applications in related problems. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 109–119, 2000     

Minor and minimum cycle bases of a 3-connected planar graph

In this paper, we prove that if any set of ｜E（G）｜- ｜V（G）｜ ＋ 1 facial cycles of a 3-connected planar graph G embedded in the plane doesn＇t form a minimum cycle base of G, then any minimum cycle base of G contains a separating cycle, and G has a minor isomorphic to T6, where T6 is the graph obtained from the complete graph K6 by deleting a path with four edges.     

A conjecture of Borodin and a coloring of Grünbaum

In 1976, Borodin conjectured that every planar graph has a 5‐coloring such that the union of every k color classes with 1 ≤ k ≤ 4 induces a (k—1)‐degenerate graph. We prove the existence of such a coloring using 18 colors. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:139–147, 2008     

List‐coloring the square of a subcubic graph

The square G² of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G²) ≤ 7. Kostochka and Woodall conjectured that for every graph, the list‐chromatic number of G² equals the chromatic number of G², that is, χ_l(G²) = χ(G²) for all G. If true, this conjecture (together with Thomassen's result) implies that every planar graph G with Δ(G) = 3 satisfies χ_l(G²) ≤ 7. We prove that every connected graph (not necessarily planar) with Δ(G) = 3 other than the Petersen graph satisfies χ_l(G²) ≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 7, then χ_l(G²) ≤ 7. Dvo?ák, ?krekovski, and Tancer showed that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 10, then χ_l(G²) ≤6. We improve the girth bound to show that if G is a planar graph with Δ(G) = 3 and g(G) ≥ 9, then χ_l(G²) ≤ 6. All of our proofs can be easily translated into linear‐time coloring algorithms. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 65–87, 2008     

Chromatic capacity and graph operations

The chromatic capacityχ_cap(G) of a graph G is the largest k for which there exists a k-coloring of the edges of G such that, for every coloring of the vertices of G with the same colors, some edge is colored the same as both its vertices. We prove that there is an unbounded function f:N→N such that χ_cap(G)?f(χ(G)) for almost every graph G, where χ denotes the chromatic number. We show that for any positive integers n and k with k?n/2 there exists a graph G with χ(G)=n and χ_cap(G)=n-k, extending a result of Greene. We obtain bounds on that are tight as r→∞, where is the complete n-partite graph with r vertices in each part. Finally, for any positive integers p and q we construct a graph G with χ_cap(G)+1=χ(G)=p that contains no odd cycles of length less than q.     

若干联图的邻点可区别-点边全染色

设G(V,E)是简单图,k是正整数.从V(G)∪E(G)到{1,2,…,k}的映射f被称作G的邻点可区别-点边全染色,当且仅当:■uv∈E(G),f(u)≠f(uv),f(v)≠f(uv),■uv∈E(G),C(u)≠C(v),且称最小的数k为G的邻点可区别-点边全色数.其中C(u)={f(u)}∪{f(uv)|uv∈E(G)},研究了一些联图的邻点可区别-点边全染色法,得到了它们的色数.     

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     

具有唯一4度最大度点的图的全色数

一个图Ｇ的全色数χ_T（Ｇ）是使得Ｖ（Ｇ）∪Ｅ（Ｇ）中相邻或相关联元素均染不同颜色的最少颜色数．文中证明了，若图Ｇ只有唯一的一个４度最大度点，则χ_T（Ｇ）＝Δ（Ｇ）＋１．