JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2020, Vol. 55 ›› Issue (9): 51-53.doi: 10.6040/j.issn.1671-9352.0.2019.089

Previous Articles    

Vertex-disjoint triangles in anti-d-degenerate graphs

NIU Bei*, ZHANG Xin   

  1. School of Mathematics and Statistics, Xidian University, Xian 710071, Shaanxi, China
  • Published:2020-09-17

PDF (PC)

419

Abstract: A graph G is an anti-d-degenerate graph if its complement graph (-overG) is a d-degenerate graph. It is proved that every anti-d-degenerate graph G with |G|=3k and δ(G)≥k≥26d contains k vertex-disjoint triangles, where d≥2.

Key words: (anti)-d-degenerate graph, independent set, vertex-disjoint triangle, equitable coloring

CLC Number: 

  • O157.5
[1] BONDY J A, MURTY U S R. Graph theory with applications[M]. London: Macmillan Education UK, 1976.
[2] CORRÁDI K, HAJNAL A. On the maximal number of independent circuits in a graph[J]. Acta Mathematica Academiae Scientiarum Hungaricae, 1963, 14(3/4):423-439.
[3] ERDÖS P. Theory of graphs and its Applications[M]. Prague: Czech Acad Sci Pub, 1964: 159.
[4] HAJNAL A, SZEMERÉDI E. Proof of a conjecture of P. Erdös[J]. Combinatorial Theory and Its Application, 1970, 2:601-623.
[5] KIERSTEAD H A, KOSTOCHKA A V. Equitable versus nearly equitable coloring and the Chen-Lih-Wu conjecture[J]. Combinatorica, 2010, 30(2):201-216
[6] KIERSTEAD H A, KOSTOCHKA A V. Ore-type versions of Brooks' theorem[J]. Journal of Combinatorial Theory, Series B, 2009, 99(2):298-305.
[1] WU Fang-lan1, ZUO Lian-cui2*. Equitable colorings of a special class of Cartesian products of graphs [J]. J4, 2013, 48(4): 20-24.
[2] LIU Shu-li. Improper equitable coloring of forests [J]. J4, 2010, 45(8): 40-42.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd