Optimal Chromatic Bound for (P3 ∨ P2, House)-Free Graphs

被引：0
作者：
Li, Rui [1 ]
Li, Jinfeng [1 ]
Wu, Di [2 ]
机构：
[1] Hohai Univ, Sch Math, 8 West Focheng Rd, Nanjing 211100, Peoples R China
[2] Nanjing Inst Technol, Dept Math & Phys, 1 Hongjing Ave, Nanjing 211167, Peoples R China
来源：
GRAPHS AND COMBINATORICS | 2025年 / 41卷 / 01期
关键词：
Chromatic number; Clique number; chi-binding function; (P-3 boolean OR P-2)- freegraphs; CHI;
D O I：
10.1007/s00373-025-02894-w
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Let F and H be two vertex disjoint graphs. The union F U H is the graph with V(F boolean OR H) = V(F) boolean OR V(H) and E(F boolean OR H) = E(F) boolean OR E(H). We use P-k to denote a path on k vertices and use house to denote the complement of P-5 . In this paper, we show that if G is a (P-3 boolean OR P-2 , house)-free graph, then chi(G) <= 2 omega (G) . Moreover, this bound is optimal when omega(G) >= 2.
引用
收藏
页数：15
相关论文
共 21 条
  • [1] Bounding χ in terms of ω and Δ for some classes of graphs
    Aravind, N. R.
    Karthick, T.
    Subramanian, C. R.
    [J]. DISCRETE MATHEMATICS, 2011, 311 (12) : 911 - 920
  • [2] Bharathi AP, 2018, GRAPH COMBINATOR, V34, P97, DOI 10.1007/s00373-017-1870-8
  • [3] Bondy A., 2008, Graph Theory, DOI [10.1007/978-1-84628-970-5, DOI 10.1007/978-1-84628-970-5]
  • [4] An optimal χ-bound for ( P 6, diamond)-free graphs
    Cameron, Kathie
    Huang, Shenwei
    Merkel, Owen
    [J]. JOURNAL OF GRAPH THEORY, 2021, 97 (03) : 451 - 465
  • [5] Perfect coloring and linearly χ-bound P6-Free graphs
    Choudum, S. A.
    Karthick, T.
    Shalu, M. A.
    [J]. JOURNAL OF GRAPH THEORY, 2007, 54 (04) : 293 - 306
  • [6] The strong perfect graph theorem
    Chudnovsky, Maria
    Robertson, Neil
    Seymour, Paul
    Thomas, Robin
    [J]. ANNALS OF MATHEMATICS, 2006, 164 (01) : 51 - 229
  • [7] Erdos Paul, 1959, Canadian Journal of Mathematics, V11, P34, DOI 10.4153/CJM-1959-003-9
  • [8] ON GRAPHS WITHOUT P-5 AND (P-5)OVER-BAR
    FOUQUET, JL
    GIAKOUMAKIS, V
    MAIRE, F
    THUILLIER, H
    [J]. DISCRETE MATHEMATICS, 1995, 146 (1-3) : 33 - 44
  • [9] Geisser M., 2022, Ph.D. thesis
  • [10] Karthick T, 2018, GRAPH COMBINATOR, V34, P677, DOI 10.1007/s00373-018-1905-9
123