Dense Graphs with Small Clique Number

被引:16
|
作者
Goddard, Wayne [1 ,2 ]
Lyle, Jeremy [2 ,3 ]
机构
[1] Clemson Univ, Sch Comp, Clemson, SC 29631 USA
[2] Clemson Univ, Dept Math Sci, Clemson, SC USA
[3] Univ So Mississippi, Dept Math, Hattiesburg, MS 39406 USA
关键词
dense graphs; clique; coloring; homomorphism; minimum degree; TRIANGLE-FREE GRAPHS; LARGE MINIMUM DEGREE; BIPARTITE;
D O I
10.1002/jgt.20505
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We consider the structure of K(r)-free graphs with large minimum degree, and show that such graphs with minimum degree delta>(2r-5)n/(2r-3) are homomorphic to the join K(r-3)vH, where H is a triangle-free graph. In particular this allows us to generalize results from triangle-free graphs and show that K(r)-free graphs with such a minimum degree have chromatic number at most r+1. We also consider the minimum-degree thresh-olds for related properties. (c) 2010 Wiley Periodicals, Inc. J Graph Theory 66: 319-331, 2011
引用
收藏
页码:319 / 331
页数:13
相关论文
共 50 条
  • [21] List-Coloring Claw-Free Graphs with Small Clique Number
    Louis Esperet
    András Gyárfás
    Frédéric Maffray
    Graphs and Combinatorics, 2014, 30 : 365 - 375
  • [22] List-Coloring Claw-Free Graphs with Small Clique Number
    Esperet, Louis
    Gyarfas, Andras
    Maffray, Frederic
    GRAPHS AND COMBINATORICS, 2014, 30 (02) : 365 - 375
  • [23] K-Clique-Graphs for Dense Subgraph Discovery
    Nikolentzos, Giannis
    Meladianos, Polykarpos
    Stavrakas, Yannis
    Vazirgiannis, Michalis
    MACHINE LEARNING AND KNOWLEDGE DISCOVERY IN DATABASES, ECML PKDD 2017, PT I, 2017, 10534 : 617 - 633
  • [24] On graphs with equal coprime index and clique number
    Patil, Chetan
    Khandekar, Nilesh
    Joshi, Vinayak
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2023, 20 (03) : 235 - 243
  • [25] Colouring perfect graphs with bounded clique number
    Chudnovsky, Maria
    Lagoutte, Aurelie
    Seymour, Paul
    Spirkl, Sophie
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 122 : 757 - 775
  • [26] A New Spectral Bound on the Clique Number of Graphs
    Bulo, Samuel Rota
    Pelillo, Marcello
    STRUCTURAL, SYNTACTIC, AND STATISTICAL PATTERN RECOGNITION, 2010, 6218 : 680 - 689
  • [27] The clique number and some Hamiltonian properties of graphs
    Li, Rao
    CONTRIBUTIONS TO MATHEMATICS, 2021, 4 : 20 - 22
  • [28] The Zagreb indices of graphs with a given clique number
    College of Science, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
    Appl Math Lett, 6 (1026-1030):
  • [29] On Local Connectivity of Graphs with Given Clique Number
    holtkamp, Andreas
    Volkmann, Lutz
    JOURNAL OF GRAPH THEORY, 2010, 63 (03) : 192 - 197
  • [30] NoteOn the Structure of Graphs with Bounded Clique Number
    Stephan Brandt
    Combinatorica, 2003, 23 : 693 - 696