Coloring_of_some_crown-free_graphs

2023/07/22 by Wu, Di, Xu, Baogang
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2307.11946

Abstract

Let G and H be two vertex disjoint graphs. The \em union G∪ H is the graph with V(G∪ H)=V(G)∪ (H) and E(G∪ H)=E(G)∪ E(H). The \em join G+H is the graph with V(G+H)=V(G)+V(H) and E(G+H)=E(G)∪ E(H)∪\xy | x∈ V(G), y∈ V(H)\. We use P_k to denote a \em path on k vertices, use \em fork to denote the graph obtained from K_1,3 by subdividing an edge once, and use \em crown to denote the graph K₁+K_1,3. In this paper, we show that (\romannumeral 1) χ(G)≤(3)/(2)(ω²(G)-ω(G)) if G is (crown, P₅)-free, (\romannumeral 2) χ(G)≤(1)/(2)(ω²(G)+ω(G)) if G is (crown, fork)-free, and (\romannumeral 3) χ(G)≤(1)/(2)ω²(G)+(3)/(2)ω(G)+1 if G is (crown, P₃∪ P₂)-free.

Related

• Coloring of some (P₂∪ P₄)-free graphs
• A tight linear bound to the chromatic number of (P₅, K₁+(K₁∪ K₃))-free graphs
• Optimal chromatic bound for (P₃∪ P₂, house)-free graphs
• A tight linear chromatic bound for (P₃∪ P₂, W₄)-free graphs
• Perfect divisibility and coloring of some fork-free graphs