Coloring (P₅, kite)-free graphs with small cliques

DOI10.1016/J.DAM.2023.11.025MaRDI QIDQ6180573zbMATH OpenOpenAlexFDO

Authors Shenwei Huang, Yiao Ju, T. Karthick

Publication date 22 December 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.08631

zbMATH Keywords

chromatic numberclique numbergraph classes\( P_5\)-free graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Abstract: Let $P_n$ and $K_n$ denote the induced path and complete graph on $n$ vertices, respectively. The {em kite} is the graph obtained from a $P_4$ by adding a vertex and making it adjacent to all vertices in the $P_4$ except one vertex with degree 1. A graph is ($P_5$, kite)-free if it has no induced subgraph isomorphic to a $P_5$ or a kite. For a graph $G$, the chromatic number of $G$ (denoted by $chi(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 ($P_5$, kite)-free graphs with small clique number. It is known that every ($P_5$,~kite, $K_3$)-free graph $G$ satisfies $chi(G)leq3$, every ($P_5$,~kite, $K_4$)-free graph $G$ satisfies $chi(G)leq4$, and that every ($P_5$,~kite, $K_5$)-free graph $G$ satisfies $chi(G)leq6$. In this paper, we showed the following: $$ Every ($P_5$, kite, $K_6$)-free graph $G$ satisfies $chi(G)leq7$. $$ Every ($P_5$, kite, $K_7$)-free graph $G$ satisfies $chi(G)leq9$. We also give examples to show that the above bounds are tight.

Recommendations

• Non-perfect \((P_5, C_5, K_5 -e)\)-free graphs are 5-colorable
• On the chromatic number of \(P_5\)-free graphs with no large intersecting cliques
• Improved bounds on the chromatic number of (\(P_5\), flag)-free graphs
• Perfect coloring and linearly χ-boundP6-free graphs
• Coloring of \((P_5, 4\)-wheel)-free graphs

Cites work

• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• Coloring graphs with no induced five‐vertex path or gem
• Coloring the hypergraph of maximal cliques of a graph with no long path
• Forbidden subgraphs and 3-colorings
• Linear chromatic bounds for a subfamily of \(3K_{1}\)-free graphs
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Square-Free Graphs with No Six-Vertex Induced Path
• Sur le coloriage des graphs
• The chromatic number of \(\{P_5,K_4\}\)-free graphs
• The strong perfect graph theorem
• Triangle-free \(2P_3\)-free graphs are 4-colorable
• Triangle-free graphs and forbidden subgraphs
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• \((2P_2,K_4)\)-free graphs are 4-colorable
• \(K_{4}\)-free graphs with no odd holes
• \(\chi\)-bounds, operations, and chords

Cited in

(2)

• Structure of some \(( P_7, C_4)\)-free graphs with application to colorings
• Coloring graphs without induced \(P_5\) or \(K_5-e\)

This page was built for publication: Coloring (\(P_5\), kite)-free graphs with small cliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6180573)