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

DOI10.1016/J.DAM.2023.11.025zbMATH Open1529.05065arXiv2204.08631OpenAlexW4388750232MaRDI QIDQ6180573FDOQ6180573

Authors: Shenwei Huang, Yiao Ju, T. Karthick 

Publication date: 22 December 2023

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

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.

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

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

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)

Cites Work

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

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)