Search

A star coloring of an undirected graph G is a coloring of the vertices of G such that (i) no two adjacent vertices receive the same color, and (ii) no path on 4 vertices is bi-colored. The star chromatic number of G, χs(G), is the minimum number of colors needed to star color G. In this paper, we show that if a graph G is either non-regular subcubic or cubic with girth at least 6, then χs(G) ≤ 6, and the bound can be realized in linear time. [ABSTRACT FROM AUTHOR]

We consider constrained proper edge colorings of the following type: Given a positive integer j and a family Ƒ of connected graphs oil three or more vertices, we require that the subgraph formed by the union of any j color classes has no copy of any member of Ƒ. This generalizes some well-known types of colorings such as acyclic edge colorings, distance-2 edge colorings, low treewidth edge colorings, etc. For such a generalization of restricted colorings, we obtain an upper bound of O(dmax(θ,1)) of the minimum number of colors used in such a coloring. Here d refers to the maximum degree of the graph, and θ is a parameter defined by θ = θ (j, Ƒ) = SUPH∈ Ƒ (|V(H)|-2/(|E(H)-j) where SUP stands for the supremum. Our proof is based on probabilistic arguments. In particular, we obtain O(d) upper bounds for proper edge colorings with various interesting restrictions placed on the union of color classes. For example, we obtain O(d) upper bounds on edge colorings with restrictions such as (i) the union of any three color classes should be an outerplanar graph, (ii) the union of any four color classes should have treewidth at most 2, (iii) the union of any five color classes should be planar, (iv) the union of any 16 color classes should be 5-degenerate, etc. We also consider generalizations where we require simultaneously for several pairs (ji,Ƒi (i = 1,…,s) that the union of any ji color classes has no copy of any member of Ƒi and obtain upper bounds on the corresponding chromatic indices. As a corollary, we obtain that each of the four restrictions above can be satisfied simultaneously using O(d) colors. Some ways of improving the bounds are sketched. O) Also, if we drop the requirement that the edge coloring be proper, then an O(dθ upper bound on the chromatic index is established. Further, the stated upper bounds are also bounds for the list analogues of these edge colorings. [ABSTRACT FROM AUTHOR]

We study the problem of efficiently sampling k-colorings of bipartite graphs. We show that a class of markov chains cannot be used as efficient samplers. Precisely, we show that, for any k, 6 ≤ k ≤ n1/3-∈, ∈ < 0 fixed, almost every bipartite graph on n + n vertices is such that the mixing time of any ergodic markov chain asymptotically uniform on its k-colorings is exponential in n/k² (if it is allowed to only change the colors of O(n/k) vertices in a single transition step). This kind of exponential time mixing is called torpid mixing. As a corollary, we show that there are (for every large n) bipartite graphs on 2n vertices with Δ(G) = Ω(ln n) such that for every k, 6 ≤ k ≤ Δ/(6 ln Δ), each member of a large class of chains mixes torpidly. We also show that these negative results hold true for H-colorings of bipartite graphs provided H contains a spanning complete bipartite subgraph. We also present explicit examples of colorings (k-colorings or H-colorings) which admit 1-cautious chains that are ergodic and are shown to have exponential mixing time. While, for fixed k or fixed H, such negative results are implied by the work of [2], our results are more general in that they allow k or H to vary with n. [ABSTRACT FROM AUTHOR]

Consider the general partitioning (GP) problem defined as follows: Partition the vertices of a graph into k parts W1, …, Wk satisfying a polynomial time verifiable property. In particular, consider properties (introduced by T. Feder, P. Hell, S. Klein, and R. Motwani, in “Proceedings of the Annual ACM Symposium on Theory of Computing (STOC ''99), 1999” and) specified by a pattern of requirements as to which Wi forms a sparse or dense subgraph and which pairs Wi, Wj form a sparse or dense or an arbitrary (no restriction) bipartite subgraph. The sparsity or density is specified by upper or lower bounds on the edge density d ∈ [0, 1], which is the fraction of actual edges present to the maximum number of edges allowed. This problem is NP-hard even for some fixed patterns and includes as special cases well-known NP-hard problems like k-coloring (each d(Wi) = 0; each d(Wi, Wj) is arbitrary), bisection (k = 2; &z.sfnc;W1&z.sfnc; = &z.sfnc;W2&z.sfnc;; d(W1, W2) ≤ b), and also other problems like finding a clique/independent set of specified size. We show that GP is solvable in polynomial time almost surely over random instances with a planted partition of desired type, for several types of pattern requirement. The algorithm is based on the approach of growing BFS trees outlined by C. R. Subramanian (in “Proceedings of the 8th Annual European Symposium on Algorithms (ESA ''00), 2000,” pp. 415–426). [Copyright &y& Elsevier]

We obtain some improved upper and lower bounds on the oriented chromatic number for different classes of products of graphs. [ABSTRACT FROM AUTHOR]