On the existence of specific stars in planar graphs

被引:20
作者
Harant, Jochen
Jendrol, Stanislav
机构
[1] Tech Univ Ilmenau, Inst Math, D-98684 Ilmenau, Germany
[2] Safarik Univ, Inst Math, SK-04154 Kosice, Slovakia
关键词
planar graphs; polytopal graphs; paths; stars; Kotzig's type theorem;
D O I
10.1007/s00373-007-0747-7
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Given a graph G, a (k;a,b,c)-star in G is a subgraph isomorphic to a star K-1,K-3 with a central vertex of degree k and three leaves of degrees a, b and c in G. The main result of the paper is: Every planar graph G of minimum degree at least 3 contains a (k;a,b,c)-star with a <= b <= c and (i) k = 3, <= n 10, or (ii) k = 4, a = 4, 4 <= b <= 10, or (iii) k = 4, a = 5, 5 <= b <= 9, or (iv) k = 4, 6 <= a <= 7, 6 <= b <= 8, or (v) k = 5, 4 <= a <= 5, 5 <= b <= 6 and 5 <= c <= 7, or (vi) k = 5 and a = b = c = 6.
引用
收藏
页码:529 / 543
页数:15
相关论文
共 27 条
  • [1] Ando K., 1993, ANN M MATH SOC JAP
  • [2] [Anonymous], ANN NEW YORK ACAD SC
  • [3] [Anonymous], 1955, MAT FYZ CASOPIS SLOV
  • [4] Covering planar graphs with forests
    Balogh, J
    Kochol, M
    Pluhár, A
    Yu, XX
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 94 (01) : 147 - 158
  • [5] DVORAK Z, IN PRESS EUROPEAN J
  • [6] Enomoto H, 1999, J GRAPH THEOR, V30, P191, DOI 10.1002/(SICI)1097-0118(199903)30:3<191::AID-JGT4>3.3.CO
  • [7] 2-O
  • [8] Subgraphs with restricted degrees of their vertices in planar 3-connected graphs
    Fabrici, I
    Jendrol, S
    [J]. GRAPHS AND COMBINATORICS, 1997, 13 (03) : 245 - 250
  • [9] FABRICI I, IN PRESS DISCUSS MAT
  • [10] The four color problem
    Franklin, P
    [J]. AMERICAN JOURNAL OF MATHEMATICS, 1922, 44 : 225 - 236