A tight linear bound to the chromatic number of (P5,K1+(K1∪K3))(P_5, K_1+(K_1\cup K_3))-free graphs

preprint2022arXivOpen access

Abstract

Let F1F_1 and F2F_2 be two disjoint graphs. The union F1∪F2F_1\cup F_2 is a graph with vertex set V(F1)∪V(F2)V(F_1)\cup V(F_2) and edge set E(F1)∪E(F2)E(F_1)\cup E(F_2), and the join F1+F2F_1+F_2 is a graph with vertex set V(F1)∪V(F2)V(F_1)\cup V(F_2) and edge set $E(F_1)\cup E(F_2)\cup \{xy\;|\; x\in V(F_1)\mbox{ and } y\in V(F_2)\}$. In this paper, we present a characterization to (P5,K1∪K3)(P_5, K_1\cup K_3)-free graphs, prove that χ(G)≤2ω(G)−1χ(G)\le 2ω(G)-1 if GG is (P5,K1∪K3)(P_5, K_1\cup K_3)-free. Based on this result, we further prove that χ(G)≤χ(G)\le max{2ω(G),15}\{2ω(G),15\} if GG is a (P5,K1+(K1∪K3))(P_5,K_1+( K_1\cup K_3))-free graph, and construct an infinite family of (P5,K1+(K1∪K3))(P_5, K_1+( K_1\cup K_3))-free graphs such that every graph GG in the family satisfies χ(G)=2ω(G)χ(G)=2ω(G).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.