Acyclic vertex coloring of graphs of maximum degree 5

An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of G, denoted a(G), is the minimum number of colors required for acyclic vertex coloring of graph G. For a family F of graphs, the acyclic chromatic number of F, denoted by a(F), is defined as the maximum a(G) over all the graphs G∈F. In this paper we show that a(F)=8 where F is the family of graphs of maximum degree 5 and give a linear time algorithm to achieve this bound.     

Subgraph‐avoiding coloring of graphs

Given a “forbidden graph” F and an integer k, an F‐avoiding k‐coloring of a graph G is a k‐coloring of the vertices of G such that no maximal F‐free subgraph of G is monochromatic. The F‐avoiding chromatic number ac_F(G) is the smallest integer k such that G is F‐avoiding k‐colorable. In this paper, we will give a complete answer to the following question: for which graph F, does there exist a constant C, depending only on F, such that ac_F(G) ? C for any graph G? For those graphs F with unbounded avoiding chromatic number, upper bounds for ac_F(G) in terms of various invariants of G are also given. Particularly, we prove that ${{ac}}_{{{F}}}({{G}})\le {{2}}\lceil\sqrt{{{n}}}\rceil+{{1}}Given a “forbidden graph” F and an integer k, an F‐avoiding k‐coloring of a graph G is a k‐coloring of the vertices of G such that no maximal F‐free subgraph of G is monochromatic. The F‐avoiding chromatic number ac_F(G) is the smallest integer k such that G is F‐avoiding k‐colorable. In this paper, we will give a complete answer to the following question: for which graph F, does there exist a constant C, depending only on F, such that ac_F(G) ? C for any graph G? For those graphs F with unbounded avoiding chromatic number, upper bounds for ac_F(G) in terms of various invariants of G are also given. Particularly, we prove that ${{ac}}_{{{F}}}({{G}})\le {{2}}\lceil\sqrt{{{n}}}\rceil+{{1}}$, where n is the order of G and F is not K_k or $\overline{{{K}}_{{{k}}}}$. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 300–310, 2010     

On a conjecture by Plummer and Toft

The cyclic chromatic number χ_c(G) of a 2‐connected plane graph G is the minimum number of colors in an assigment of colors to the vertices of G such that, for every face‐bounding cycle f of G, the vertices of f have different colors. Plummer and Toft proved that, for a 3‐connected plane graph G, under the assumption Δ*(G) ≥ 42, where Δ*(G) is the size of a largest face of G, it holds that χ_c(G) ≤ Δ*(G) + 4. They conjectured that, if G is a 3‐connected plane graph, then χ_c>(G) ≤ Δ*(G) + 2. In the article the conjecture is proved for Δ*(G) ≥ 24. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 177–189, 1999     

A Sharp Threshold for k‐Colorability

Let k be a fixed integer and f_k(n, p) denote the probability that the random graph G(n, p) is k‐colorable. We show that for k≥3, there exists d_k(n) such that for any ϵ>0, (1) As a result we conclude that for sufficiently large n the chromatic number of G(n, d/n) is concentrated in one value for all but a small fraction of d>1. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 63–70, 1999     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Dirac's map-color theorem for choosability

It is proved that the choice number of every graph G embedded on a surface of Euler genus ε ≥ 1 and ε ≠ 3 is at most the Heawood number and that the equality holds if and only if G contains the complete graph K_H(ε) as a subgraph. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 327–339, 1999     

An upper bound for the Folkman number F(3, 3; 5)

Let F(p, q; r) denote the minimum number of vertices in a graph G that has the properties (1) G contains no complete subgraph on r vertices, and (2) any green-red coloring of the edges of G yields a green complete subgraph on p vertices or a red complete subgraph on q vertices. Folkman proved the existence of F(p, q; r) whenever r > max {p, q}. We show F(3, 3; 5) ≤ 17, improving a bound due to Irving and an earlier bound due to Graham and Spencer. © 1993 John Wiley & Sons, Inc.     

The total chromatic number of regular graphs of high degree

The total chromatic number χT (G) of a graph G is the minimum number of colors needed to color the edges and the vertices of G so that incident or adjacent elements have distinct colors. We show that if G is a regular graph and d(G) 32 |V (G)| + 263 , where d(G) denotes the degree of a vertex in G, then χT (G) d(G) + 2.     

On K(3)4 of curves over number fields

In this paper we consider the group K ₄ ⁽³⁾ (F) of a field, in case F is the function field of a smooth geometrically irreducible curve over a number field. We do this using the complexes constructed in [4], together with an auxiliary complex. On the image in K ₄ ⁽³⁾ (F) of those complexes, we derive a formula for the Beilinson regulator, and compute an approximation of the boundary map at the closed points of the curve in the localization sequence. We give a way of finding examples of elliptic curves E with elements in K ₄ ⁽³⁾ (E), and in some cases use computer calculations to check numerically the relation between the regulator and the L-function, as conjectured by Beilinson. Oblatum 10-IX-1995 & 8-I-1996     

Rainbow faces in edge‐colored plane graphs

A face of an edge‐colored plane graph is called rainbow if the number of colors used on its edges is equal to its size. The maximum number of colors used in an edge coloring of a connected plane graph Gwith no rainbow face is called the edge‐rainbowness of G. In this paper we prove that the edge‐rainbowness of Gequals the maximum number of edges of a connected bridge face factor H of G, where a bridge face factor H of a plane graph Gis a spanning subgraph H of Gin which every face is incident with a bridge and the interior of any one face f∈F(G) is a subset of the interior of some face f′∈F(H). We also show upper and lower bounds on the edge‐rainbowness of graphs based on edge connectivity, girth of the dual graphs, and other basic graph invariants. Moreover, we present infinite classes of graphs where these equalities are attained. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 84–99, 2009     

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     

A lower bound for partial list colorings

Let G be an n-vertex graph with list-chromatic number χ_ℓ. Suppose that each vertex of G is assigned a list of t colors. Albertson, Grossman, and Haas [1] conjecture that at least t_n/χ_ℓ vertices can be colored from these lists. We prove a lower bound for the number of colorable vertices. As a corollary, we show that at least of the conjectured number can be colored. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 390–393, 1999     

Four-Cycle Systems with Two-Regular Leaves

 In this paper we settle the existence problem for 4-cycle systems of K _n −E(F) and of 2K _n −E(F) for all 2-regular subgraphs F. Received: February 5, 1999?Final version received: October 25, 1999     

On the adjacent-vertex-strongly-distinguishing total coloring of graphs

For any vertex u∈V(G), let T_N(U)={u}∪{uv|uv∈E(G), v∈v(G)}∪{v∈v(G)|uv∈E(G)}and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C_f(u)={f(x)|x∈TN(U)}. For any two adjacent vertices x and y of V(G)such that C_f(x)≠C_f(y), we refer to f as a k-avsdt-coloring of G("avsdt"is the abbreviation of"adjacent-vertex-strongly- distinguishing total"). The avsdt-coloring number of G, denoted by X_(ast)(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We proveΔ(G) 1≤X_(ast)(G)≤Δ(G) 2 for any tree or unique cycle graph G.     

Rainbows in the Hypercube

Let Q_n be a hypercube of dimension n, that is, a graph whose vertices are binary n-tuples and two vertices are adjacent iff the corresponding n-tuples differ in exactly one position. An edge coloring of a graph H is called rainbow if no two edges of H have the same color. Let f(G,H) be the largest number of colors such that there exists an edge coloring of G with f(G,H) colors such that no subgraph isomorphic to H is rainbow. In this paper we start the investigation of this anti-Ramsey problem by providing bounds on f(Q_n,Q_k) which are asymptotically tight for k = 2 and by giving some exact results.     

Une preuve simple des conjectures de Langlands pour GL(n) sur un corps p-adique

Let F be a finite extension of ℚ _p . For each integer n≥1, we construct a bijection from the set ?_F ⁰ (n) of isomorphism classes of irreducible degree n representations of the (absolute) Weil group of F, onto the set ? _F ⁰ (n) of isomorphism classes of smooth irreducible supercuspidal representations of GL _n (F). Those bijections preserve epsilon factors for pairs and hence we obtain a proof of the Langlands conjectures for GL _n over F, which is more direct than Harris and Taylor’s. Our approach is global, and analogous to the derivation of local class field theory from global class field theory. We start with a result of Kottwitz and Clozel on the good reduction of some Shimura varieties and we use a trick of Harris, who constructs non-Galois automorphic induction in certain cases. Oblatum 1-III-1999 & 21-VII-1999 / Published online: 29 November 1999     

On the list dynamic coloring of graphs

A proper vertex coloring of a graph G is called a dynamic coloring if for every vertex v of degree at least 2, the neighbors of v receive at least two different colors. Assume that is the minimum number k such that for every list assignment of size k to each vertex of G, there is a dynamic coloring of G such that every vertex is colored with a color from its list. In this paper, it is proved that if G is a graph with no component isomorphic to C₅ and Δ(G)≥3, then , where Δ(G) is the maximum degree of G. This generalizes a result due to Lai, Montgomery and Poon which says that under the same assumptions χ₂(G)≤Δ(G)+1. Among other results, we determine , for every natural number n.     

Star coloring of sparse graphs

A proper coloring of the vertices of a graph is called a star coloring if the union of every two color classes induces a star forest. The star chromatic number χ_s(G) is the smallest number of colors required to obtain a star coloring of G. In this paper, we study the relationship between the star chromatic number χ_s(G) and the maximum average degree Mad(G) of a graph G. We prove that:

• 1. If G is a graph with , then χ_s(G)≤4.
• 2. If G is a graph with and girth at least 6, then χ_s(G)≤5.
• 3. If G is a graph with and girth at least 6, then χ_s(G)≤6.

These results are obtained by proving that such graphs admit a particular decomposition into a forest and some independent sets. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 201–219, 2009     

Codimensions of Newton strata for <Emphasis Type="Italic">SL</Emphasis><Subscript>3</Subscript>(<Emphasis Type="Italic">F</Emphasis>) in the Iwahori case

We study the Newton stratification on SL ₃(F), where F is a Laurent power series field. We provide a formula for the codimensions of the Newton strata inside each component of the affine Bruhat decomposition on SL ₃(F). These calculations are related to the study of certain affine Deligne–Lusztig varieties. In particular, we describe a method for determining which of these varieties is non-empty in the case of SL ₃(F).