Indexed by:
Abstract:
A graph G is called (H1, H2) -free if G contains no induced subgraph isomorphic to H1 or H2 . Let Pk be a path with k vertices and Cs,t,k (s≤ t) be a graph consisting of two intersecting complete graphs Ks+k and Kt+k with exactly k common vertices. In this paper, using an iterative method, we prove that the class of (P5, Cs,t,k) -free graphs with clique number ω has a polynomial χ -binding function f(ω) = c(s, t, k) ωmax{s,k} . In particular, we give two improved chromatic bounds: every (P5, butterfly) -free graph G has χ(G)≤32ω(G)(ω(G)-1) ; every (P5, C1 , 3) -free graph G has χ(G) ≤ 9 ω(G) . © 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
Keyword:
Reprint 's Address:
Email:
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: