Home About us Contact
|
Home About us Contact | ||
|
|
||
Graph Theory (graph + theory)
Selected AbstractsSubgraph-avoiding coloring of graphsJOURNAL OF GRAPH THEORY, Issue 4 2010Jia Shen Abstract Given a "forbidden graph" F and an integer k, an F-avoiding k-coloring of a graph G is a k -coloring of the vertices of G such that no maximal F -free subgraph of G is monochromatic. The F-avoiding chromatic numberacF(G) is the smallest integer k such that G is F -avoiding k -colorable. In this paper, we will give a complete answer to the following question: for which graph F, does there exist a constant C, depending only on F, such that acF(G) , C for any graph G? For those graphs F with unbounded avoiding chromatic number, upper bounds for acF(G) in terms of various invariants of G are also given. Particularly, we prove that , where n is the order of G and F is not Kk or . © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 300,310, 2010 [source] Multi-coloring the Mycielskian of graphsJOURNAL OF GRAPH THEORY, Issue 4 2010Wensong Lin Abstract A k -fold coloring of a graph is a function that assigns to each vertex a set of k colors, so that the color sets assigned to adjacent vertices are disjoint. The kth chromatic number of a graph G, denoted by ,k(G), is the minimum total number of colors used in a k -fold coloring of G. Let µ(G) denote the Mycielskian of G. For any positive integer k, it holds that ,k(G) + 1,,k(µ(G)),,k(G) + k (W. Lin, Disc. Math., 308 (2008), 3565,3573). Although both bounds are attainable, it was proved in (Z. Pan, X. Zhu, Multiple coloring of cone graphs, manuscript, 2006) that if k,2 and ,k(G),3k,2, then the upper bound can be reduced by 1, i.e., ,k(µ(G)),,k(G) + k,1. We conjecture that for any n,3k,1, there is a graph G with ,k(G)=n and ,k(µ(G))=n+ k. This is equivalent to conjecturing that the equality ,k(µ(K(n, k)))=n+k holds for Kneser graphs K(n, k) with n,3k,1. We confirm this conjecture for k=2, 3, or when n is a multiple of k or n,3k2/ln k. Moreover, we determine the values of ,k(µ(C2q+1)) for 1,k,q. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 311,323, 2010 [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] Path homomorphisms, graph colorings, and boolean matricesJOURNAL OF GRAPH THEORY, Issue 3 2010Jaroslav Ne Abstract We investigate bounds on the chromatic number of a graph G derived from the nonexistence of homomorphisms from some path into some orientation of G. The condition is often efficiently verifiable using boolean matrix multiplications. However, the bound associated to a path depends on the relation between the "algebraic length" and "derived algebraic length" of . This suggests that paths yielding efficient bounds may be exponentially large with respect to G, and the corresponding heuristic may not be constructive. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 198,209, 2010 [source] Balanced judicious bipartitions of graphsJOURNAL OF GRAPH THEORY, Issue 3 2010Baogang Xu Abstract A bipartition of the vertex set of a graph is called balanced if the sizes of the sets in the bipartition differ by at most one. B. Bollobás and A. D. Scott, Random Struct Alg 21 (2002), 414,430 conjectured that if G is a graph with minimum degree of at least 2 then V(G) admits a balanced bipartition V1, V2 such that for each i, G has at most |E(G)|/3 edges with both ends in Vi. The minimum degree condition is necessary, and a result of B. Bollobás and A. D. Scott, J. Graph Theory 46 (2004), 131,143 shows that this conjecture holds for regular graphs G(i.e., when ,(G)=,(G)). We prove this conjecture for graphs G with ; hence, it holds for graphs ]ensuremathG with . © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 210,225, 2010 [source] d -Regular graphs of acyclic chromatic index at least d+2JOURNAL OF GRAPH THEORY, Issue 3 2010Manu Basavaraju Abstract An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a,(G). It was conjectured by Alon, Sudakov and Zaks (and earlier by Fiamcik) that a,(G),,+2, where ,=,(G) denotes the maximum degree of the graph. Alon et al. also raised the question whether the complete graphs of even order are the only regular graphs which require ,+2 colors to be acyclically edge colored. In this article, using a simple counting argument we observe not only that this is not true, but in fact all d -regular graphs with 2n vertices and d>n, requires at least d+ 2 colors. We also show that a,(Kn, n),n+ 2, when n is odd using a more non-trivial argument. (Here Kn, n denotes the complete bipartite graph with n vertices on each side.) This lower bound for Kn, n can be shown to be tight for some families of complete bipartite graphs and for small values of n. We also infer that for every d, n such that d,5, n,2d+ 3 and dn even, there exist d -regular graphs which require at least d+2-colors to be acyclically edge colored. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 226,230, 2010 [source] Non-rainbow colorings of 3-, 4- and 5-connected plane graphsJOURNAL OF GRAPH THEORY, Issue 2 2010k Dvo Abstract We study vertex-colorings of plane graphs that do not contain a rainbow face, i.e., a face with vertices of mutually distinct colors. If G is a 3 -connected plane graph with n vertices, then the number of colors in such a coloring does not exceed . If G is 4 -connected, then the number of colors is at most , and for n,3(mod8), it is at most . Finally, if G is 5 -connected, then the number of colors is at most . The bounds for 3 -connected and 4 -connected plane graphs are the best possible as we exhibit constructions of graphs with colorings matching the bounds. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 129,145, 2010 [source] Families of pairs of graphs with a large number of common cardsJOURNAL OF GRAPH THEORY, Issue 2 2010Andrew Bowler Abstract The vertex-deleted subgraph G,v, obtained from the graph G by deleting the vertex v and all edges incident to v, is called a card of G. The deck of G is the multiset of its unlabelled vertex-deleted subgraphs. The number of common cards of G and H (or between G and H) is the cardinality of the multiset intersection of the decks of G and H. In this article, we present infinite families of pairs of graphs of order n , 4 that have at least common cards; we conjecture that these, along with a small number of other families constructed from them, are the only pairs of graphs having this many common cards, for sufficiently large n. This leads us to propose a new stronger version of the Reconstruction Conjecture. In addition, we present an infinite family of pairs of graphs with the same degree sequence that have common cards, for appropriate values of n, from which we can construct pairs having slightly fewer common cards for all other values of n,10. We also present infinite families of pairs of forests and pairs of trees with and common cards, respectively. We then present new families that have the maximum number of common cards when one graph is connected and the other disconnected. Finally, we present a family with a large number of common cards, where one graph is a tree and the other unicyclic, and discuss how many cards are required to determine whether a graph is a tree. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 146,163, 2010 [source] Proof of a conjecture on fractional Ramsey numbersJOURNAL OF GRAPH THEORY, Issue 2 2010Jason Brown Abstract Jacobson, Levin, and Scheinerman introduced the fractional Ramsey function rf (a1, a2, ,, ak) as an extension of the classical definition for Ramsey numbers. They determined an exact formula for the fractional Ramsey function for the case k=2. In this article, we answer an open problem by determining an explicit formula for the general case k>2 by constructing an infinite family of circulant graphs for which the independence numbers can be computed explicitly. This construction gives us two further results: a new (infinite) family of star extremal graphs which are a superset of many of the families currently known in the literature, and a broad generalization of known results on the chromatic number of integer distance graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 164,178, 2010 [source] A structure theorem for graphs with no cycle with a unique chord and its consequencesJOURNAL OF GRAPH THEORY, Issue 1 2010Nicolas Trotignon Abstract We give a structural description of the class ,, of graphs that do not contain a cycle with a unique chord as an induced subgraph. Our main theorem states that any connected graph in ,, is either in some simple basic class or has a decomposition. Basic classes are chordless cycles, cliques, bipartite graphs with one side containing only nodes of degree 2 and induced subgraphs of the famous Heawood or Petersen graph. Decompositions are node cutsets consisting of one or two nodes and edge cutsets called 1-joins. Our decomposition theorem actually gives a complete structure theorem for ,,, i.e. every graph in ,, can be built from basic graphs that can be explicitly constructed, and gluing them together by prescribed composition operations, and all graphs built this way are in ,,. This has several consequences: an ,,(nm) -time algorithm to decide whether a graph is in ,,, an ,,(n+ m) -time algorithm that finds a maximum clique of any graph in ,,, and an ,,(nm) -time coloring algorithm for graphs in ,,. We prove that every graph in ,, is either 3-colorable or has a coloring with , colors where , is the size of a largest clique. The problem of finding a maximum stable set for a graph in ,, is known to be NP-hard. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 31,67, 2010 [source] Grünbaum colorings of toroidal triangulationsJOURNAL OF GRAPH THEORY, Issue 1 2010Michael O. Albertson Abstract We prove that if G is a triangulation of the torus and ,(G),5, then there is a 3-coloring of the edges of G so that the edges bounding every face are assigned three different colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 68,81, 2010 [source] Solution of a conjecture of Tewes and Volkmann regarding extendable cycles in in-tournamentsJOURNAL OF GRAPH THEORY, Issue 1 2010Dirk Meierling Abstract A directed cycle C of a digraph D is extendable if there exists a directed cycle C, in D that contains all vertices of C and an additional one. In 1989, Hendry defined a digraph D to be cycle extendable if it contains a directed cycle and every non-Hamiltonian directed cycle of D is extendable. Furthermore, D is fully cycle extendable if it is cycle extendable and every vertex of D belongs to a directed cycle of length three. In 2001, Tewes and Volkmann extended these definitions in considering only directed cycles whose length exceed a certain bound 3,k Independent sets of maximal size in tensor powers of vertex-transitive graphsJOURNAL OF GRAPH THEORY, Issue 4 2009Cheng Yeaw Ku Abstract Let G be a connected, nonbipartite vertex-transitive graph. We prove that if the only independent sets of maximal cardinality in the tensor product G × G are the preimages of the independent sets of maximal cardinality in G under projections, then the same holds for all finite tensor powers of G, thus providing an affirmative answer to a question raised by Larose and Tardif (J Graph Theory 40(3) (2002), 162,171). © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 295-301, 2009 [source] K6 -minors in triangulations and complete quadrangulationsJOURNAL OF GRAPH THEORY, Issue 4 2009Raiji Mukae Abstract In this paper, we shall prove that a projective-planar (resp., toroidal) triangulation G has K6 as a minor if and only if G has no quadrangulation isomorphic to K4 (resp., K5 ) as a subgraph. As an application of the theorems, we can prove that Hadwiger's conjecture is true for projective-planar and toroidal triangulations. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 302-312, 2009 [source] Unavoidable parallel minors of 4-connected graphsJOURNAL OF GRAPH THEORY, Issue 4 2009Carolyn Chun A parallel minor is obtained from a graph by any sequence of edge contractions and parallel edge deletions. We prove that, for any positive integer k, every internally 4-connected graph of sufficiently high order contains a parallel minor isomorphic to a variation of K4,k with a complete graph on the vertices of degree k, the k -partition triple fan with a complete graph on the vertices of degree k, the k -spoke double wheel, the k -spoke double wheel with axle, the (2k+1)-rung Möbius zigzag ladder, the (2k)-rung zigzag ladder, or Kk. We also find the unavoidable parallel minors of 1-, 2-, and 3-connected graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 313-326, 2009 [source] Forbidden induced bipartite graphsJOURNAL OF GRAPH THEORY, Issue 3 2009Peter Allen Abstract Given a fixed bipartite graph H, we study the asymptotic speed of growth of the number of bipartite graphs on n vertices which do not contain an induced copy of H. Whenever H contains either a cycle or the bipartite complement of a cycle, the speed of growth is . For every other bipartite graph except the path on seven vertices, we are able to find both upper and lower bounds of the form . In many cases we are able to determine the correct value of c. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 219,241, 2009 [source] Weight choosability of graphsJOURNAL OF GRAPH THEORY, Issue 3 2009Tomasz Bartnicki Abstract Suppose the edges of a graph G are assigned 3-element lists of real weights. Is it possible to choose a weight for each edge from its list so that the sums of weights around adjacent vertices were different? We prove that the answer is positive for several classes of graphs, including complete graphs, complete bipartite graphs, and trees (except K2). The argument is algebraic and uses permanents of matrices and Combinatorial Nullstellensatz. We also consider a directed version of the problem. We prove by an elementary argument that for digraphs the answer to the above question is positive even with lists of size two. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 242,256, 2009 [source] The size of edge chromatic critical graphs with maximum degree 6JOURNAL OF GRAPH THEORY, Issue 2 2009Rong Luo Abstract In 1968, Vizing [Uaspekhi Mat Nauk 23 (1968) 117,134; Russian Math Surveys 23 (1968), 125,142] conjectured that for any edge chromatic critical graph with maximum degree , . This conjecture has been verified for . In this article, by applying the discharging method, we prove the conjecture for . © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 149,171, 2009 [source] Total domination in 2-connected graphs and in graphs with no induced 6-cyclesJOURNAL OF GRAPH THEORY, Issue 1 2009Michael A. Henning Abstract A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number ,t(G) of G. It is known [J Graph Theory 35 (2000), 21,45] that if G is a connected graph of order n,>,10 with minimum degree at least 2, then ,t(G),,,4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2-connected graphs, as well as for connected graphs with no induced 6-cycle. We prove that if G is a 2-connected graph of order n,>,18, then ,t(G),,,6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n,>,18 with minimum degree at least 2 and no induced 6-cycle, then ,t(G),,,6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55,79, 2009 [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] On a conjecture about edge irregular total labelingsJOURNAL OF GRAPH THEORY, Issue 4 2008Stephan Brandt Abstract As our main result, we prove that for every multigraph G,=,(V, E) which has no loops and is of order n, size m, and maximum degree there is a mapping such that for every with . Functions with this property were recently introduced and studied by Ba,a et al. and were called edge irregular total labelings. Our result confirms a recent conjecture of Ivan,o and Jendrol, about such labelings for dense graphs, for graphs where the maximum and minimum degree are not too different in terms of the order, and also for large graphs of bounded maximum degree. © 2008 Wiley Periodicals, Inc. J Graph Theory 57: 333,343, 2008 [source] On conjectures of Frankl and El-ZaharJOURNAL OF GRAPH THEORY, Issue 4 2008Bernardo Llano Abstract An induced subgraph of a graph is called a derived subgraph of if contains no isolated vertices. An edge e of is said to be residual if e occurs in more than half of the derived subgraphs of . In this article, we prove that every simple graph with at least one edge contains a non-residual edge. This was conjectured by El-Zahar in 1997. © 2008 Wiley Periodicals, Inc. J Graph Theory 57: 344,352, 2008 [source] Rank-width is less than or equal to branch-widthJOURNAL OF GRAPH THEORY, Issue 3 2008Sang-il Oum Abstract We prove that the rank-width of the incidence graph of a graph G is either equal to or exactly one less than the branch-width of G, unless the maximum degree of G is 0 or 1. This implies that rank-width of a graph is less than or equal to branch-width of the graph unless the branch-width is 0. Moreover, this inequality is tight. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 239,244, 2008 [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] Graph classes characterized both by forbidden subgraphs and degree sequencesJOURNAL OF GRAPH THEORY, Issue 2 2008Michael D. Barrus Abstract Given a set of graphs, a graph G is -free if G does not contain any member of as an induced subgraph. We say that is a degree-sequence-forcing set if, for each graph G in the class of -free graphs, every realization of the degree sequence of G is also in . We give a complete characterization of the degree-sequence-forcing sets when has cardinality at most two. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 131,148, 2008 [source] Maximum acyclic and fragmented sets in regular graphsJOURNAL OF GRAPH THEORY, Issue 2 2008Penny Haxell Abstract We show that a typical d -regular graph G of order n does not contain an induced forest with around vertices, when n,,,d,,,1, this bound being best possible because of a result of Frieze and ,uczak [6]. We then deduce an affirmative answer to an open question of Edwards and Farr (see [4]) about fragmentability, which concerns large subgraphs with components of bounded size. An alternative, direct answer to the question is also given. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 149,156, 2008 [source] Scaled Gromov hyperbolic graphsJOURNAL OF GRAPH THEORY, Issue 2 2008Edmond Jonckheere Abstract In this article, the ,-hyperbolic concept, originally developed for infinite graphs, is adapted to very large but finite graphs. Such graphs can indeed exhibit properties typical of negatively curved spaces, yet the traditional ,-hyperbolic concept, which requires existence of an upper bound on the fatness , of the geodesic triangles, is unable to capture those properties, as any finite graph has finite ,. Here the idea is to scale , relative to the diameter of the geodesic triangles and use the Cartan,Alexandrov,Toponogov (CAT) theory to derive the thresholding value of ,diam below which the geometry has negative curvature properties. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 157,180, 2008 [source] On k -domination and minimum degree in graphsJOURNAL OF GRAPH THEORY, Issue 1 2008Odile Favaron Abstract A subset S of vertices of a graph G is k -dominating if every vertex not in S has at least k neighbors in S. The k -domination number is the minimum cardinality of a k -dominating set of G. Different upper bounds on are known in terms of the order n and the minimum degree of G. In this self-contained article, we present an Erdös-type result, from which some of these bounds follow. In particular, we improve the bound for , proved by Chen and Zhou in 1998. Furthermore, we characterize the extremal graphs in the inequality , if , of Cockayne et al. This characterization generalizes that of graphs realizing . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 33,40, 2008 [source] Vertex suppression in 3-connected graphsJOURNAL OF GRAPH THEORY, Issue 1 2008Matthias Kriesell Abstract To suppress a vertex in a finite graph G means to delete it and add an edge from a to b if a, b are distinct nonadjacent vertices which formed the neighborhood of . Let be the graph obtained from by suppressing vertices of degree at most 2 as long as it is possible; this is proven to be well defined. Our main result states that every 3-connected graph G has a vertex x such that is 3-connected unless G is isomorphic to , , or to a wheel for some . This leads to a generator theorem for 3-connected graphs in terms of series parallel extensions. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 41,54, 2008 [source] On k -detour subgraphs of hypercubesJOURNAL OF GRAPH THEORY, Issue 1 2008Nana Arizumi Abstract A spanning subgraph G of a graph H is a k - detour subgraph of H if for each pair of vertices , the distance, , between x and y in G exceeds that in H by at most k. Such subgraphs sometimes also are called additive spanners. In this article, we study k -detour subgraphs of the n -dimensional cube, , with few edges or with moderate maximum degree. Let denote the minimum possible maximum degree of a k -detour subgraph of . The main result is that for every and On the other hand, for each fixed even and large n, there exists a k -detour subgraph of with average degree at most . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 55,64, 2008 [source]
| | ||||||||||||||||||