2024/12/19 by Ran Chen, Ran, Chen, Zhang xiaowen +1
Computer Science · Engineering · #Graph Labeling and Dimension Problems #Advanced Graph Theory Research #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2412.14524
We denote a path on t vertices as Pt and a cycle on t vertices as Ct. For two vertex-disjoint graphs G1 and G2, the \em union G1∪ G2 is the graph with V(G1∪ G2)=V(G1)∪ V(G2) and E(G1∪ G2)=E(G1)∪ E(G2). A \em diamond (resp. \em gem) is a graph consisting of a P3 (resp. P4) and a new vertex adjacent to all vertices of the P3 (resp. P4), and a \em butterfly is a graph consisting of two triangles that share one vertex. In this paper, we show that χ(G)≤ 3ω(G)-2 if G is a (P2∪ P4, gem)-free graph, χ(G)≤ (ω(G)2+3ω(G)-2)/(2) if G is a (P2∪ P4, butterfly)-free graph. We also study the class of (P2∪ P4, diamond)-free graphs, and show that, for such a graph G, χ(G)≤4 if ω(G)=2, χ(G)≤7 if ω(G)=3, χ(G)≤9 if ω(G)=4, and χ(G)≤2ω(G)-1 if ω(G)≥ 5. Moreover, we prove that G is perfect if G is (P2∪ P4, diamond, C5)-free with ω(G)≥5.