We show that every plane graph with maximum face size four in which all faces of size four are vertex-disjoint is cyclically 5-colorable. This answers a question of Albertson whether graphs drawn in the plane with all crossings independent are 5-colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory
domingo, 22 de noviembre de 2009
Coloring plane graphs with independent crossings
We show that every plane graph with maximum face size four in which all faces of size four are vertex-disjoint is cyclically 5-colorable. This answers a question of Albertson whether graphs drawn in the plane with all crossings independent are 5-colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory
Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree
A balloon in a graph G is a maximal 2-edge-connected subgraph incident to exactly one cut-edge of G. Let b(G) be the number of balloons, let c(G) be the number of cut-edges, and let [alpha][prime](G) be the maximum size of a matching. Let be the family of connected (2r+1)-regular graphs with n vertices, and let . For , we prove the sharp inequalities c(G)[les][r(n-2)-2]/(2r2+2r-1)-1 and [alpha][prime](G)[ges]n/2-rb/(2r+1). Using b[les][(2r-1)n+2]/(4r2+4r-2), we obtain a simple proof of the bound proved by Henning and Yeo. For each of these bounds and each r, the approach using balloons allows us to determine the infinite family where equality holds. For the total domination number [gamma]t(G) of a cubic graph, we prove [gamma]t(G)[les]n/2-b(G)/2 (except that [gamma]t(G) may be n/2-1 when b(G)=3 and the balloons cover all but one vertex). With [alpha][prime](G)[ges]n/2-b(G)/3 for cubic graphs, this improves the known inequality [gamma]t(G)[les][alpha][prime](G). © 2009 Wiley Periodicals, Inc. J Graph Theory
Choosability of toroidal graphs without short cycles
Let G be a toroidal graph without cycles of a fixed length k, and [chi]l(G) the list chromatic number of G. We establish tight upper bounds of [chi]l(G) for the following values of k: © 2009 Wiley Periodicals, Inc. J Graph Theory
The geometry of t-spreads in k-walk-regular graphs
A graph is walk-regular if the number of closed walks of length [ell] rooted at a given vertex is a constant through all the vertices for all [ell]. For a walk-regular graph G with d+1 different eigenvalues and spectrally maximum diameter D=d, we study the geometry of its d-spreads, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a simplex (or tetrahedron in a three-dimensional case) and we compute its parameters. Moreover, the results are generalized to the case of k-walk-regular graphs, a family which includes both walk-regular and distance-regular graphs, and their t-spreads or vertices at distance t from each other. © 2009 Wiley Periodicals, Inc. J Graph Theory
On Ramsey-type positional games
Beck introduced the concept of Ramsey games by studying the game versions of Ramsey and van der Waerden theorems. We contribute to this topic by investigating games corresponding to structural extensions of Ramsey and van der Waerden theorems - the theorem of Brauer, structural and restricted Ramsey theorems. © 2009 Wiley Periodicals, Inc. J Graph Theory
On recognizing graphs by numbers of homomorphisms
Let hom (G, H) be the number of homomorphisms from a graph G to a graph H. A well-known result of Lovász states that the function hom (·, H) from all graphs uniquely determines the graph H up to isomorphism. We study this function restricted to smaller classes of graphs. We show that several natural classes (2-degenerate graphs and graphs homomorphic to an arbitrary non-bipartite graph) are sufficient to recognize all graphs, and provide a description of graph properties that are recognizable by graphs with bounded tree-width. © 2009 Wiley Periodicals, Inc. J Graph Theory
Brown, IBM Unveil Multimillion-Dollar Supercomputer
Brown University and IBM today announced the opening of a multimillion-dollar supercomputer at Brown's Center for Computation and Visualization.
Preservation and destruction of periodic orbits by symplectic integrators
Suscribirse a:
Entradas (Atom)