Coloring \ P 2 P 3 , house \ -free graphs with - 1 colors

DOI10.1016/J.DAM.2023.09.003MaRDI QIDQ6143841zbMATH OpenOpenAlexFDO

Authors Rong Chen, Kaiyang Lan, Yidong Zhou

Publication date 24 January 2024

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

Full work available at URL https://doi.org/10.1016/j.dam.2023.09.003

zbMATH Keywords

chromatic numberforbidden induced subgraphsperfect graphs

Mathematics Subject Classification ID

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

Recommendations

• Borodin-Kostochka's conjecture on \(\{P_2 \cup P_3, C_4\}\)-free graphs
• Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors
• Borodin-Kostochka conjecture holds for \(\overline{K_{1 , 3}} \)-free graphs
• Borodin-Kostochka conjecture holds for odd-hole-free graphs
• Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs

Cites work

• A strengthening of Brooks' theorem
• A survey of -boundedness
• Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs
• Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors
• Coloring Claw-Free Graphs with \Delta-1 Colors
• Graphs with chromatic number close to maximum degree
• scientific article; zbMATH DE number 3719178 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Note on the colouring of graphs
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Some results on Reed's conjecture about \(\omega ,\Delta \), and \(\chi \) with respect to \(\alpha \)
• The strong perfect graph theorem

Cited in

(9)

• Borodin-Kostochka conjecture holds for odd-hole-free graphs
• Partitioning of a graph into induced subgraphs not containing prescribed cliques
• Borodin-Kostochka conjecture holds for \(\overline{K_{1 , 3}} \)-free graphs
• Borodin-Kostochka's conjecture on \(\{P_2 \cup P_3, C_4\}\)-free graphs
• The chromatic number of \(\{P_2 \cup P_3,\text{ banner}\}\)-free graphs
• Optimal coloring of \((P_2 + P_3, \mathrm{gem})\)-free graphs
• The chromatic number of odd-hole-free graphs
• On the chromatic number of \(\{\text{bull, diamond}\}\)-free graphs
• Tight chromatic bounds for (P₂ + P₄, K₄ - e)-free graphs

This page was built for publication: Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors

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