Home About us Contact
|
Home About us Contact | ||
|
|
||
Free Graphs (free + graph)
Selected AbstractsColoring H-free hypergraphsRANDOM STRUCTURES AND ALGORITHMS, Issue 1 2010Tom Bohman Abstract Fix r , 2 and a collection of r -uniform hypergraphs . What is the minimum number of edges in an -free r -uniform hypergraph with chromatic number greater than k? We investigate this question for various . Our results include the following: An (r,l)-system is an r -uniform hypergraph with every two edges sharing at most l vertices. For k sufficiently large, there is an (r,l)-system with chromatic number greater than k and number of edges at most c(kr,1 log k)l/(l,1), where This improves on the previous best bounds of Kostochka et al. (Random Structures Algorithms 19 (2001), 87,98). The upper bound is sharp apart from the constant c as shown in (Random Structures Algorithms 19 (2001) 87,98). The minimum number of edges in an r -uniform hypergraph with independent neighborhoods and chromatic number greater than k is of order kr+1/(r,1) log O(1)k as k , ,. This generalizes (aside from logarithmic factors) a result of Gimbel and Thomassen (Discrete Mathematics 219 (2000), 275,277) for triangle-free graphs. Let T be an r -uniform hypertree of t edges. Then every T -free r -uniform hypergraph has chromatic number at most 2(r , 1)(t , 1) + 1. This generalizes the well-known fact that every T -free graph has chromatic number at most t. Several open problems and conjectures are also posed. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010 [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] Perfect coloring and linearly ,-bound P6 -free graphsJOURNAL OF GRAPH THEORY, Issue 4 2007S. A. Choudum Abstract We derive decomposition theorems for P6, K1 + P4 -free graphs, P5, K1 + P4 -free graphs and P5, K1 + C4 -free graphs, and deduce linear ,-binding functions for these classes of graphs (here, Pn (Cn) denotes the path (cycle) on n vertices and K1 + G denotes the graph obtained from G by adding a new vertex and joining it with every vertex of G). Using the same techniques, we also obtain an optimal ,-binding function for P5, C4 -free graphs which is an improvement over that given in [J. L. Fouquet, V. Giakoumakis, F. Maire, and H. Thuillier, 1995, Discrete Math, 146, 33,44.]. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 293,306, 2007 [source] Uncountable graphs and invariant measures on the set of universal countable graphsRANDOM STRUCTURES AND ALGORITHMS, Issue 3 2010Fedor Petrov Abstract We give new examples and describe the complete lists of all measures on the set of countable homogeneous universal graphs and Ks -free homogeneous universal graphs (for s , 3) that are invariant with respect to the group of all permutations of the vertices. Such measures can be regarded as random graphs (respectively, random Ks -free graphs). The well-known example of Erdös,Rényi (ER) of the random graph corresponds to the Bernoulli measure on the set of adjacency matrices. For the case of the universal Ks -free graphs there were no previously known examples of the invariant measures on the space of such graphs. The main idea of our construction is based on the new notions of measurable universal, and topologically universal graphs, which are interesting themselves. The realization of the construction can be regarded as two-step randomization for universal measurable graph : "randomization in vertices" and "randomization in edges." For Ks -free, s , 3, there is only randomization in vertices of the measurable graphs. The completeness of our lists is proved using the important theorem by Aldous about S, -invariant matrices, which we reformulate in appropriate way. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010 [source] | ||||||||||