Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree

DOI10.1007/s10878-015-9929-zzbMath1364.05031OpenAlexW1063412800MaRDI QIDQ512863

Baoyindureng Wu, Xiao Wang

Publication date: 3 March 2017

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-015-9929-z

zbMATH Keywords

chromatic numberinduced subgraphtriangle-free graphforbidden subgraph

Mathematics Subject Classification ID

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

Related Items (2)

The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs

Cites Work

• A bound on the chromatic number of graphs without certain induced subgraphs
• Induced subtrees in graphs of large chromatic number
• 3-colorability and forbidden subgraphs. I: Characterizing pairs
• Triangle-free graphs and forbidden subgraphs
• Vertex colouring and forbidden subgraphs -- a survey
• Graph Theory and Probability
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree