Nonrepetitive vertex colorings of graphs

We prove new upper bounds on the Thue chromatic number of an arbitrary graph and on the facial Thue chromatic number of a plane graph in terms of its maximum degree.     

Conditional colorings of graphs

For an integer r>0, a conditional(k,r)-coloring of a graph G is a proper k-coloring of the vertices of G such that every vertex of degree at least r in G will be adjacent to vertices with at least r different colors. The smallest integer k for which a graph G has a conditional (k,r)-coloring is the rth order conditional chromatic number χ_r(G). In this paper, the behavior and bounds of conditional chromatic number of a graph G are investigated.     

Consecutive colorings of graphs

In a simple graphG=(X.E) a positive integerc _i is associated with every nodei. We consider node colorings where nodei receives a setS(i) ofc _i consecutive colors andS(i)S(j)=Ø whenever nodesi andj are linked inG. Upper bounds on the minimum number of colors needed are derived. The case of perfect graphs is discussed.

---

Zusammenfassung In einem schlichten GraphenG=(X, E) gibt man jedem Knotenpunkti einen positiven ganzzahligen Wertc _i. Wir betrachten Färbungen der Knotenpunkte, bei denen jeder Knotenpunkti eine MengeS(i) vonc _i konsekutiven Farben erhält mitS(i)S(j)=Ø wenn die Kante [i.j] existiert. Obere Grenzen für die minimale Anzahl der Farben solcher Färbungen werden hergeleitet. Der Fall der perfekten Graphen wird auch kurz diskutiert.

     

Nonrepetitive colorings of graphs

A coloring of the vertices of a graph G is nonrepetitive if there is no even path in G whose first half looks the same as the second half. This notion arose as an analogue of the famous nonrepetitive sequences of Thue. We consider here the list analogue and the game analogue of nonrepetitive colorings.     

系列平行图SHMeredith图的关联着色

图的关联着色是从关联集到颜色集的一个映射,使得关联集中任何两个相邻的关联都具有不同的像.确定了Meredith图的关联色数,证明了对任意系列平行图都存在一个(Δ 2,2)-关联着色.     

Relative colorings of graphs

In this paper, the notion of relative chromatic number χ(G, H) for a pair of graphs G, H, with H a full subgraph of G, is formulated; namely, χ(G, H) is the minimum number of new colors needed to extend any coloring of H to a coloring of G. It is shown that the four color conjecture (4CC) is equivalent to the conjecture (R4CC) that χ(G, H) ≤ 4 for any (possibly empty) full subgraph H of a planar graph G and also to the conjecture (CR3CC) that χ(G, H) ≤ 3 if H is a connected and nonempty full subgraph of planar G. Finally, relative coloring theorems on surfaces other than the plane or sphere are proved.     

Adjacent strong edge colorings and total colorings of regular graphs

It is conjectured that χas(G) = χt(G) for every k-regular graph G with no C5 component (k 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V (G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.     

Acyclic edge colorings of planar graphs and seriesparallel graphs

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1. This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation of Shandong Province (Grant No. Y2008A20).     

Injective colorings of sparse graphs

Let denote the maximum average degree (over all subgraphs) of G and let χ_i(G) denote the injective chromatic number of G. We prove that if , then χ_i(G)≤Δ(G)+1; and if , then χ_i(G)=Δ(G). Suppose that G is a planar graph with girth g(G) and Δ(G)≥4. We prove that if g(G)≥9, then χ_i(G)≤Δ(G)+1; similarly, if g(G)≥13, then χ_i(G)=Δ(G).     

Linear colorings of subcubic graphs

A linear coloring of a graph is a proper coloring of the vertices of the graph so that each pair of color classes induces a union of disjoint paths. In this paper, we prove that for every connected graph with maximum degree at most three and every assignment of lists of size four to the vertices of the graph, there exists a linear coloring such that the color of each vertex belongs to the list assigned to that vertex and the neighbors of every degree-two vertex receive different colors, unless the graph is _C5$C_5$ or _K3,3$K_{3,3}$. This confirms a conjecture raised by Esperet, Montassier and Raspaud [L. Esperet, M. Montassier, and A. Raspaud, Linear choosability of graphs, Discrete Math. 308 (2008) 3938–3950]. Our proof is constructive and yields a linear-time algorithm to find such a coloring.     

Monochromatic k-edge-connection colorings of graphs

A path in an edge-colored graph $G$ is called monochromatic if any two edges on the path have the same color. For $k\ge 2$, an edge-colored graph $G$ is said to be monochromatic $k$-edge-connected if every two distinct vertices of $G$ are connected by at least $k$ edge-disjoint monochromatic paths, and $G$ is said to be uniformly monochromatic $k$-edge-connected if every two distinct vertices are connected by at least $k$ edge-disjoint monochromatic paths such that all edges of these $k$ paths are colored with a same color. We use $m{c}_k\left(G\right)$ and $um{c}_k\left(G\right)$ to denote the maximum number of colors that ensures $G$ to be monochromatic $k$-edge-connected and, respectively, $G$ to be uniformly monochromatic $k$-edge-connected. In this paper, we first conjecture that for any $k$-edge-connected graph $G$, $m{c}_k\left(G\right)=e\left(G\right)-e\left(H\right)+\lfloor \frac{k}{2}\rfloor$, where $H$ is a minimum $k$-edge-connected spanning subgraph of $G$. We verify the conjecture for $k=2$. We also prove the conjecture for $G=K_{k+1}$ and $G=K_{k,n}$ with $n\ge k\ge 3$. When $G$ is a minimal $k$-edge-connected graph, we give an upper bound of $m{c}_k\left(G\right)$, i.e., $m{c}_k\left(G\right)\le k-1$. For the uniformly monochromatic $k$-edge-connectivity, we prove that for all $k$, $um{c}_k\left(G\right)=e\left(G\right)-e\left(H\right)+1$, where $H$ is a minimum $k$-edge-connected spanning subgraph of $G$.     

Circular colorings of weighted graphs

Suppose that G is a finite simple graph and w is a weight function which assigns to each vertex of G a nonnegative real number. Let C be a circle of length t. A t-circular coloring of (G, w) is a mapping Δ of the vertices of G to arcs of C such that Δ(x)∩Δ(y) = 0 if (x, y) ∈ E(G) and Δ(x) has length w(x). The circular-chromatic number of (G, w) is the least t for which there is a t-circular coloring of (G, w). This paper discusses basic properties of circular chromatic number of a weighted graph and relations between this parameter and other graph parameters. We are particularly interested in graphs G for which the circular-chromatic number of (G, w) is equal to the fractional clique weight of (G, w) for arbitrary weight function w. We call such graphs star-superperfect. We prove that odd cycles and their complements are star-superperfect. We then prove a theorem about the circular chromatic number of lexicographic product of graphs which provides a tool of constructing new star-superperfect graphs from old ones. © 1996 John Wiley & Sons, Inc.     

Acrylic improper colorings of graphs

In this article, we introduce the new notion of acyclic improper colorings of graphs. An improper coloring of a graph is a vertex-coloring in which adjacent vertices are allowed to have the same color, but each color class V_i satisfies some condition depending on i. Such a coloring is acyclic if there are no alternating 2-colored cycles. We prove that every outerplanar graph can be acyclically 2-colored in such a way that each monochromatic subgraph has degree at most five and that this result is best possible. For planar graphs, we prove some negative results and state some open problems. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 97–107, 1999     

Acyclic colorings of planar graphs

A coloring of the vertices of a graph byk colors is called acyclic provided that no circuit is bichromatic. We prove that every planar graph has an acyclic coloring with nine colors, and conjecture that five colors are sufficient. Other results on related types of colorings are also obtained; some of them generalize known facts about “point-arboricity”. Research supported in part by the Office of Naval Research under Grant N00014-67-A-0103-0003.     

Oriented list colorings of graphs

A 2‐assignment on a graph G = (V,E) is a collection of pairs L(v) of allowed colors specified for all vertices v ∈V. The graph G (with at least one edge) is said to have oriented choice number 2 if it admits an orientation which satisfies the following property: For every 2‐assignment there exists a choice c(v)∈L(v) for all v ∈V such that (i) if c(v) = c(w), then vw ∉ E, and (ii) for every ordered pair (a,b) of colors, if some edge oriented from color a to color b occurs, then no edge is oriented from color b to color a. In this paper we characterize the following subclasses of graphs of oriented choice number 2: matchings; connected graphs; graphs containing at least one cycle. In particular, the first result (which implies that the matching with 11 edges has oriented choice number 2) proves a conjecture of Sali and Simonyi. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 217–229, 2001     

Face colorings of embedded graphs

We characterize those graphs which have at least one embedding into some surface such that the faces can be properly colored in four or fewer colors. Embeddings into both orientable and nonorientable surfaces are considered.     

Orientable edge colorings of graphs

An edge coloring of a graph is orientable if and only if it is possible to orient the edges of the graph so that the color of each edge is determined by the head of its corresponding oriented arc. The goals of this paper include finding a forbidden substructure characterization of orientable colorings and giving a linear time recognition algorithm for orientable colorings.An edge coloring is lexical if and only if it is possible to number the vertices of the graph so that the color of each edge is determined by its lower endpoint. Lexical colorings are, of course, the orientable colorings in which the underlying orientation is acyclic. Lexical colorings play an important role in Canonical Ramsey theory, and it is this standpoint that motivates the current study.