Indexed by:
Abstract:
A graph G is called (H1, H2)-free if G contains no induced subgraph isomorphic to H(1 )or H-2. Let P(k )be a path with k vertices and C-s,C- t,C- k (s <= t) be a graph consisting of two intersecting complete graphs K(s+k )and K(t+k )with exactly k common vertices. In this paper, using an iterative method, we prove that the class of (P5,C-s,C-t,C-k)-free graphs with clique number omega has a polynomial chi-binding function f(omega) = c(s, t, k) omega(max{s, k}). In particular, we give two improved chromatic bounds: every (P5, butterfly)-free graph G has chi (G) <= 3/2 omega (G)(omega(G)-1); every (P-5,C-1,C-3)-free graph G has chi (G) <= 9 omega(G).
Keyword:
Reprint 's Address:
Email:
Version:
Source :
JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN: 1382-6905
Year: 2023
Issue: 3
Volume: 46
0 . 9
JCR@2023
0 . 9 0 0
JCR@2023
JCR Journal Grade:3
CAS Journal Grade:4
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: