Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors

DOI10.1016/j.dam.2023.09.003OpenAlexW4386691136MaRDI QIDQ6143841

Kaiyang Lan, Yidong Zhou, Rong Chen

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 numberperfect graphsforbidden induced subgraphs

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)

Cites Work

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