A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs

DOI10.1007/s00373-023-02642-yOpenAlexW4362553893MaRDI QIDQ2701401

Wei Dong, Yian Xu, Bao-Gang Xu

Publication date: 28 April 2023

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberinduced subgraph\(P_5\)-free

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (3)

Coloring graphs without induced \(P_5\) or \(K_5-e\) ⋮ Improved bounds on the chromatic number of (\(P_5\), flag)-free graphs ⋮ Divisibility and coloring of some \(P_5\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chromatic number of \(P_5\)-free graphs: Reed's conjecture
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• On the chromatic number of \((P_{5},K_{2,t})\)-free graphs
• The strong perfect graph theorem
• A bound on the chromatic number of graphs without certain induced subgraphs
• Dominating cliques in \(P_ 5\)-free graphs
• Coloring the hypergraph of maximal cliques of a graph with no long path
• On the chromatic number of \(2 K_2\)-free graphs
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Vertex colouring and forbidden subgraphs -- a survey
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• The chromatic number of \(\{P_5,K_4\}\)-free graphs
• Coloring of \((P_5, 4\)-wheel)-free graphs
• On the chromatic number of some \(P_5\)-free graphs
• Graph Theory and Probability
• Perfect coloring and linearly χ-boundP6-free graphs
• On the chromatic number of (P_{5},windmill)-free graphs
• A survey of χ‐boundedness
• A BOUND FOR THE CHROMATIC NUMBER OF (, GEM)-FREE GRAPHS
• Perfect divisibility and 2‐divisibility
• On graphs with no induced five‐vertex path or paraglider
• An optimal χ‐bound for (P6, diamond)‐free graphs
• Coloring graphs with no induced five‐vertex path or gem

This page was built for publication: A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs