We prove that the facial nonrepetitive chromatic number of any outerplanar graph is at most 11 and of any planar graph is at most 22.
Barát and Varjú @cite_33 and K "u ndgen and Pelsmajer @cite_30 independently showed that @math if @math is outerplanar and, more generally, @math if @math has treewidth at most @math . (Barát and Varjú proved the latter bound with @math while K "u ndgen and Pelsmajer proved it with @math .) The bound of @math for @math -trees is tight if @math (trees), but it is not known if it is tight for other values of @math . Even the upper bound of 12 for outerplanar graphs may not be tight, as no outerplanar graph with nonrepetititive chromatic number greater than 7 is known @cite_33 .
@cite_30 @cite_33
2052210031 2070606919 2011571064 2950981509
We define the notions tree-depth and upper chromatic number of a graph and show their relevance to local-global problems for graph partitions. In particular we show that the upper chromatic number coincides with the maximal function which can be locally demanded in a bounded coloring of any proper minor closed class of graphs. The rich interplay of these notions is applied to a solution of bounds of proper minor closed classes satisfying local conditions. In particular, we prove the following result:For every graph M and a finite set F of connected graphs there exists a (universal) graph U = U(M, F) ∈ Forbh(F) such that any graph G ∈ Forbh(F) which does not have M as a minor satisfies G → U (i.e. is homomorphic to U).This solves the main open problem of restricted dualities for minor closed classes and as an application it yields the bounded chromatic number of exact odd powers of any graph in an arbitrary proper minor closed class. We also generalize the decomposition theorem of [M. DeVos, G. Ding, B. Oporowski, D.P. Sanders, B. Reed, P. Seymour, D. Vertigan, Excluding any graph as a minor allows a low tree-width 2-coloring, J. Combin. Theory Ser. B 91 (2004) 25-41]. Consider a drawing of a graph G in the plane such that crossing edges are coloured differently. The minimum number of colours, taken over all drawings of G, is the classical graph parameter thickness. By restricting the edges to be straight, we obtain the geometric thickness. By additionally restricting the vertices to be in convex position, we obtain the book thickness. This paper studies the relationship between these parameters and treewidth. Our first main result states that for graphs of treewidth k, the maximum thickness and the maximum geometric thickness both equal ⌈k 2⌉. This says that the lower bound for thickness can be matched by an upper bound, even in the more restrictive geometric setting. Our second main result states that for graphs of treewidth k, the maximum book thickness equals k if k ≤ 2 and equals k + 1 if k ≥ 3. This refutes a conjecture of Ganley and Heath [Discrete Appl. Math. 109(3):215-221, 2001]. Analogous results are proved for outerthickness, arboricity, and star-arboricity. We resolve the following conjecture raised by Levin together with Linial, London, and Rabinovich [16]. Let Z ∞ d be the infinite graph whose vertex set is Zd and which has an edge (u,v) whenever ||u-v|| ∞ = 1. Let dim(G) be the smallest d such that G occurs as a (not necessarily induced) subgraph of Z ∞d . The growth rate of G, denoted ρ G , is the minimum ρ such that every ball of radius r > 1 in G contains at most rρ vertices. By simple volume arguments, dim(G) = Ω(ρ G ). Levin conjectured that this lower bound is tight, i.e., that dim(G) = O(ρ G ) for every graph G.Previously, it was not known whether dim(G) could be upper bounded by any function of ρ G , even in the special case of trees. We show that a weaker form of Levin's conjecture holds by proving that, for every graph G, dim(G) = O(ρ G log ρ G ). We disprove, however, the specific bound of the conjecture and show that our upper bound is tight by exhibiting graphs for which dim(G) =Ω(ρ G log ρ G ). For families of graphs which exclude a fixed minor, we salvage the strong form, showing that dim(G) = O(ρ G ). This holds also for graphs without long induced simple cycles. Our results extend to a variant of the conjecture for finite-dimensional Euclidean spaces due to Linial[15]. Let @math be a tree space (or tree network) represented by a weighted tree with @math vertices, and @math be a set of @math stochastic points in @math , each of which has a fixed location with an independent existence probability. We investigate two fundamental problems under such a stochastic setting, the closest-pair problem and the nearest-neighbor search. For the former, we study the computation of the @math -threshold probability and the expectation of the closest-pair distance of a realization of @math . We propose the first algorithm to compute the @math -threshold probability in @math time for any given threshold @math , which immediately results in an @math -time algorithm for computing the expected closest-pair distance. Based on this, we further show that one can compute a @math -approximation for the expected closest-pair distance in @math time, by arguing that the expected closest-pair distance can be approximated via @math threshold probability queries. For the latter, we study the @math most-likely nearest-neighbor search ( @math -LNN) via a notion called @math most-likely Voronoi Diagram ( @math -LVD). We show that the size of the @math -LVD @math of @math on @math is bounded by @math if the existence probabilities of the points in @math are constant-far from 0. Furthermore, we establish an @math average-case upper bound for the size of @math , by regarding the existence probabilities as i.i.d. random variables drawn from some fixed distribution. Our results imply the existence of an LVD data structure which answers @math -LNN queries in @math time using average-case @math space, and worst-case @math space if the existence probabilities are constant-far from 0. Finally, we also give an @math -time algorithm to construct the LVD data structure.