Home About us Contact
|
Home About us Contact | ||
|
|
||
Planar Graphs (planar + graph)
Selected AbstractsStar coloring planar graphs from small listsJOURNAL OF GRAPH THEORY, Issue 4 2010André Kündgen Abstract A star coloring of a graph is a proper vertex-coloring such that no path on four vertices is 2-colored. We prove that the vertices of every planar graph of girth 6 (respectively 7, 8) can be star colored from lists of size 8 (respectively 7, 6). We give an example of a planar graph of girth 5 that requires 6 colors to star color. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 324,337, 2010 [source] On the maximum number of cycles in a planar graphJOURNAL OF GRAPH THEORY, Issue 3 2008R. E. L. Aldred Abstract Let G be a graph on p vertices with q edges and let r,=,q,,,p,=,1. We show that G has at most cycles. We also show that if G is planar, then G has at most 2r,,,1,=,o(2r,,,1) cycles. The planar result is best possible in the sense that any prism, that is, the Cartesian product of a cycle and a path with one edge, has more than 2r,,,1 cycles. © Wiley Periodicals, Inc. J. Graph Theory 57: 255,264, 2008 [source] A note on the cover degeneracy of graphsJOURNAL OF GRAPH THEORY, Issue 2 2006Li Zhang Abstract We give a 4-chromatic planar graph, which admits a vertex partition into three parts such that the union of every two of them induces a forest. This solves a problem posed by Böhme. Also, by constructing an infinite sequence of graphs, we show that the cover degeneracy can be arbitrarily less than the chromatic number. © 2005 Wiley Periodicals, Inc. J Graph Theory [source] Eulerian subgraphs in 3-edge-connected graphs and Hamiltonian line graphsJOURNAL OF GRAPH THEORY, Issue 4 2003Zhi-Hong Chen Abstract In this paper, we show that if G is a 3-edge-connected graph with and , then either G has an Eulerian subgraph H such that , or G can be contracted to the Petersen graph in such a way that the preimage of each vertex of the Petersen graph contains at least one vertex in S. If G is a 3-edge-connected planar graph, then for any , G has an Eulerian subgraph H such that . As an application, we obtain a new result on Hamiltonian line graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 308,319, 2003 [source] Girth and fractional chromatic number of planar graphsJOURNAL OF GRAPH THEORY, Issue 3 2002Amir Pirnazar Abstract In 1959, even before the Four-Color Theorem was proved, Grötzsch showed that planar graphs with girth at least 4 have chromatic number at the most 3. We examine the fractional analogue of this theorem and its generalizations. For any fixed girth, we ask for the largest possible fractional chromatic number of a planar graph with that girth, and we provide upper and lower bounds for this quantity. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 201,217, 2002; DOI 10.1002/jgt10024 [source] Chiral molecules with polyhedral T, O, or I symmetry: Theoretical solution to a difficult problem in stereochemistryCHIRALITY, Issue 8 2008Sri Kamesh Narasimhan Abstract Ever since point groups of symmetry have been used to describe molecules after Van't Hoff and Le Bel proposed tetrahedral structures for carbon atoms in 1874, it remains difficult to design chiral molecules with polyhedral symmetry T, O, or I. Past theoretical and experimental studies have mainly accomplished molecular structures that have the conformations for satisfying the T symmetry. In this work, we present a general theoretical approach to construct rigid molecular structures that have permanently the symmetry of T, O, and I. This approach involves desymmetrizaton of the vertices or the edges of Platonic solid-shaped molecules with dissymmetric moieties. Using density functional theory (DFT) and assisted model building and energy refinement (AMBER) computational methods, the structure, the rigidity, and the symmetry of the molecule are confirmed by assessing the lowest energy conformation of the molecule, which is initially presented in a planar graph. This method successfully builds molecular structures that have the symmetry of T, O, and I. Interestingly, desymmetrization of the edges has a more stringent requirement of rigidity than desymmetrization of the vertices for affording the T, O, or I symmetry. Chirality, 2008. © 2008 Wiley-Liss, Inc. [source] Star coloring planar graphs from small listsJOURNAL OF GRAPH THEORY, Issue 4 2010André Kündgen Abstract A star coloring of a graph is a proper vertex-coloring such that no path on four vertices is 2-colored. We prove that the vertices of every planar graph of girth 6 (respectively 7, 8) can be star colored from lists of size 8 (respectively 7, 6). We give an example of a planar graph of girth 5 that requires 6 colors to star color. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 324,337, 2010 [source] M -degrees of quadrangle-free planar graphsJOURNAL OF GRAPH THEORY, Issue 1 2009Oleg V. Borodin Abstract The M-degree of an edge xy in a graph is the maximum of the degrees of x and y. The M-degree of a graph G is the minimum over M -degrees of its edges. In order to get upper bounds on the game chromatic number, He et al showed that every planar graph G without leaves and 4-cycles has M -degree at most 8 and gave an example of such a graph with M -degree 3. This yields upper bounds on the game chromatic number of C4 -free planar graphs. We determine the maximum possible M -degrees for planar, projective-planar and toroidal graphs without leaves and 4-cycles. In particular, for planar and projective-planar graphs this maximum is 7. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 80,85, 2009 [source] Acyclic 5-choosability of planar graphs without small cyclesJOURNAL OF GRAPH THEORY, Issue 3 2007Mickaël Montassier Abstract A proper vertex coloring of a graph G,=,(V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L -list colorable if for a given list assignment L,=,{L(v): v:,,,V}, there exists a proper acyclic coloring,,,of G such that ,(v),,, L(v) for all v,,, V. If G is acyclically L -list colorable for any list assignment with |L (v)|, k for all v,,, V, then G is acyclically k -choosable. In this article, we prove that every planar graph G without 4- and 5-cycles, or without 4- and 6-cycles is acyclically 5-choosable. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 245,260, 2007 [source] Between ends and fibersJOURNAL OF GRAPH THEORY, Issue 2 2007C. Paul Bonnington Abstract Let , be an infinite, locally finite, connected graph with distance function ,. Given a ray P in , and a constant C , 1, a vertex-sequence is said to be regulated by C if, for all n,,, never precedes xn on P, each vertex of P appears at most C times in the sequence, and . R. Halin (Math. Ann., 157, 1964, 125,137) defined two rays to be end-equivalent if they are joined by infinitely many pairwise-disjoint paths; the resulting equivalence classes are called ends. More recently H. A. Jung (Graph Structure Theory, Contemporary Mathematics, 147, 1993, 477,484) defined rays P and Q to be b-equivalent if there exist sequences and VQ regulated by some constant C , 1 such that for all n,,; he named the resulting equivalence classes b-fibers. Let denote the set of nondecreasing functions from into the set of positive real numbers. The relation (called f-equivalence) generalizes Jung's condition to . As f runs through , uncountably many equivalence relations are produced on the set of rays that are no finer than b -equivalence while, under specified conditions, are no coarser than end-equivalence. Indeed, for every , there exists an "end-defining function" that is unbounded and sublinear and such that implies that P and Q are end-equivalent. Say if there exists a sublinear function such that . The equivalence classes with respect to are called bundles. We pursue the notion of "initially metric" rays in relation to bundles, and show that in any bundle either all or none of its rays are initially metric. Furthermore, initially metric rays in the same bundle are end-equivalent. In the case that , contains translatable rays we give some sufficient conditions for every f -equivalence class to contain uncountably many g -equivalence classes (where ). We conclude with a variety of applications to infinite planar graphs. Among these, it is shown that two rays whose union is the boundary of an infinite face of an almost-transitive planar map are never bundle- equivalent. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 125,153, 2007 [source] Girth and fractional chromatic number of planar graphsJOURNAL OF GRAPH THEORY, Issue 3 2002Amir Pirnazar Abstract In 1959, even before the Four-Color Theorem was proved, Grötzsch showed that planar graphs with girth at least 4 have chromatic number at the most 3. We examine the fractional analogue of this theorem and its generalizations. For any fixed girth, we ask for the largest possible fractional chromatic number of a planar graph with that girth, and we provide upper and lower bounds for this quantity. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 201,217, 2002; DOI 10.1002/jgt10024 [source] Social network coordination and graph routingNETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2003Shmuel Onn Abstract We consider the problem of coordinating robots moving on a network. Each robot is autonomous and needs to visit various sites of the network at various times. The sequence of destinations for each robot changes dynamically and unpredictably. Recently, Onn and Tennenholtz showed that the problem can be solved by introducing a social law on the network, which, once obeyed by all robots, enables each to move to any desired destination without collisions and regardless of the actions of other robots, needing neither central coordination nor mutual communication. This social law can be derived from a suitably defined routing of the graph underlying the network. Here, we study the complexity of routing. We provide an effective characterization of 2-routable graphs, and by establishing a correspondence between hypergraph coloring and graph routing, we show that computing or approximating an optimal routing is generally hard. We also discuss routing in planar graphs, which often underlie robotic networks and show that the correspondence between coloring and routing together with the Four Color Theorem guarantee the existence of small and effectively computable routings in bipartite planar graphs of small radius. The complexity of routing arbitrary planar graphs remains open. © 2002 Wiley Periodicals, Inc. [source] Uniform random sampling of planar graphs in linear time,RANDOM STRUCTURES AND ALGORITHMS, Issue 4 2009Éric Fusy Abstract This article introduces new algorithms for the uniform random generation of labelled planar graphs. Its principles rely on Boltzmann samplers, as recently developed by Duchon, Flajolet, Louchard, and Schaeffer. It combines the Boltzmann framework, a suitable use of rejection, a new combinatorial bijection found by Fusy, Poulalhon, and Schaeffer, as well as a precise analytic description of the generating functions counting planar graphs, which was recently obtained by Giménez and Noy. This gives rise to an extremely efficient algorithm for the random generation of planar graphs. There is a preprocessing step of some fixed small cost; and the expected time complexity of generation is quadratic for exact-size uniform sampling and linear for uniform approximate-size sampling. This greatly improves on the best previously known time complexity for exact-size uniform sampling of planar graphs with n vertices, which was a little over O(n7). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source] Random maps, coalescing saddles, singularity analysis, and Airy phenomenaRANDOM STRUCTURES AND ALGORITHMS, Issue 3-4 2001Cyril Banderier Abstract A considerable number of asymptotic distributions arising in random combinatorics and analysis of algorithms are of the exponential-quadratic type, that is, Gaussian. We exhibit a class of "universal" phenomena that are of the exponential-cubic type, corresponding to distributions that involve the Airy function. In this article, such Airy phenomena are related to the coalescence of saddle points and the confluence of singularities of generating functions. For about a dozen types of random planar maps, a common Airy distribution (equivalently, a stable law of exponent ) describes the sizes of cores and of largest (multi)connected components. Consequences include the analysis and fine optimization of random generation algorithms for a multiple connected planar graphs. Based on an extension of the singularity analysis framework suggested by the Airy case, the article also presents a general classification of compositional schemas in analytic combinatorics. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 194,246, 2001 [source] | ||||||||||