Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs

DOI10.1007/s12190-020-01419-3zbMath1475.05068OpenAlexW3047417012WikidataQ123004326 ScholiaQ123004326MaRDI QIDQ2053188

Uttam K. Gupta, Dinabandhu Pradhan

Publication date: 29 November 2021

Published in: Journal of Applied Mathematics and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12190-020-01419-3

zbMATH Keywords

\((P_5, C_4)\)-free graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors ⋮ Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors ⋮ Strengthening Brooks' chromatic bound on \(P_6\)-free graphs ⋮ Borodin-Kostochka conjecture holds for odd-hole-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs with chromatic number close to maximum degree
• Some results on Reed's conjecture about \(\omega ,\Delta \), and \(\chi \) with respect to \(\alpha \)
• The chromatic number of graphs which induce neither \(K_{1,3}\) nor \(K_ 5-e\)
• Improvement on Brooks' chromatic bound for a class of graphs
• 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
• Note on the colouring of graphs
• Graphs with $\chi=\Delta$ Have Big Cliques
• Coloring Claw-Free Graphs with $\Delta-1$ Colors

This page was built for publication: Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs