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

DOI10.1007/S10878-015-9929-ZMaRDI QIDQ512863zbMATH OpenOpenAlexFDO

Authors 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) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Chromatic number of triangle-free graphs with some forbidden subgraphs
• The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices
• scientific article; zbMATH DE number 6612443
• Induced subgraphs of graphs with large chromatic number. XIII. New brooms
• Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs

Cites work

• scientific article; zbMATH DE number 1286500 (Why is no real title available?)
• scientific article; zbMATH DE number 1833071 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• 3-colorability and forbidden subgraphs. I: Characterizing pairs
• A bound on the chromatic number of graphs without certain induced subgraphs
• Graph Theory and Probability
• Induced subtrees in graphs of large chromatic number
• Triangle-free graphs and forbidden subgraphs
• Vertex colouring and forbidden subgraphs -- a survey

Cited in

(8)

• A note on the \(m\)-bounded chromatic number of a tree
• \( \chi \)-binding function for \((C_4, t\text{-broom}^+)\)-free graphs
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Chromatic number of triangle-free graphs with some forbidden subgraphs
• The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices
• A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number
• scientific article; zbMATH DE number 1833071 (Why is no real title available?)
• Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs

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

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