Nonexistence of universal graphs without some trees
Tóm tắt
IfG is a finite tree with a unique vertex of largest, and ≥4 degree which is adjacent to a leaf then there is no universal countableG-free graph.
Tài liệu tham khảo
B. Bollobás:Random graphs, 1985, Academic Press.
P. A. Catlin: Subgraphs of graphs I,Discrete Mathematics,10 (1974), 225–233.
G. Cherlin, P. Komjáth: There is no universal countable pentagon free graph,Journal of Graph Theory,18 (1994), 337–341.
G. Cherlin, N. Shi: Graphs omitting sums of complete graphs,Journal of Graph Th.,24 (1997), 237–247.
G. Cherlin, N. Shi: Graphs omitting a finite set of cycles,Journal of Graph Theory,21 (1996), 351–355.
Z. Füredi, P. Komjáth: On the existence of countable universal graphs,Journal of Graph Th.,25 (1997), 53–58.
M. Goldstern, M. Kojman: Universal arrow-free graphs,Acta Math. Hung,73 (1996), 319–326.
A. Hajnal, J. Pach: Monochromatic paths in infinite graphs, in:Finite and Infinite sets, Coll. Math. Soc. J. Bolyai,37, (Eger, Hungary, 1981), 359–369.
P. Komjáth, A. Mekler, J. Pach: Some universal graphs,Israel Journal of Mathematics,64 (1988), 158–168.
P. Komjáth, J. Pach: Universal graphs without large bipartite graphs,Mathematika,31 (1984), 282–290.
P. Komjáth, J. Pach: Universal elements and the complexity of certain classes of infinite graphs,Discrete Math. 95 (1991), 255–270.
P. Komjáth, J. Pach: The complexity of a class of infinite graphs,Combinatorica,14 (1994), 121–125.
R. Rado: Universal graphs and universal functions,Acta Arith,9 (1964), 331–340.
R. Rado: Universal graphs, inA Seminar in Graph Theory, (eds. Harary, Beineke), Holt, Rinehart, and Winston Co., 1967.
V. Rödl, L. Thoma: The complexity of cover graph recognition for some varieties of finite lattices,to appear.
N. Sauer, J. Spencer: Edge disjoint placement of graphs,Journal of Combinatorial Theory (B),25 (1978), 295–302.
G. Cherlin, N. Shi, andL. Talggren: Graphs omitting a bushy tree,Journal of Graph Th., to appear.