2022/04/19 by Shenwei Huang, Huang, Shenwei, Yiao Ju +3
Computer Science · Engineering · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2204.08631
Let Pn and Kn denote the induced path and complete graph on n vertices, respectively. The \em kite is the graph obtained from a P4 by adding a vertex and making it adjacent to all vertices in the P4 except one vertex with degree 1. A graph is (P5, kite)-free if it has no induced subgraph isomorphic to a P5 or a kite. For a graph G, the chromatic number of G (denoted by χ(G)) is the minimum number of colors needed to color the vertices of G such that no two adjacent vertices receive the same color, and the clique number of G is the size of a largest clique in G. Here, we are interested in the class of (P5, kite)-free graphs with small clique number. It is known that every (P5,~kite, K3)-free graph G satisfies χ(G)≤ 3, every (P5,~kite, K4)-free graph G satisfies χ(G)≤ 4, and that every (P5,~kite, K5)-free graph G satisfies χ(G)≤ 6. In this paper, we showed the following: \bullet Every (P5, kite, K6)-free graph G satisfies χ(G)≤ 7. \bullet Every (P5, kite, K7)-free graph G satisfies χ(G)≤ 9. We also give examples to show that the above bounds are tight.