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

DOI10.1007/S10878-015-9929-ZzbMATH Open1364.05031OpenAlexW1063412800MaRDI QIDQ512863FDOQ512863

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

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

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)

Cites Work

• Graph Theory and Probability
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Induced subtrees in graphs of large chromatic number
• Vertex colouring and forbidden subgraphs -- a survey
• A bound on the chromatic number of graphs without certain induced subgraphs
• 3-colorability and forbidden subgraphs. I: Characterizing pairs
• Title not available (Why is that?)
• Triangle-free graphs and forbidden subgraphs

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
• Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs
• Title not available (Why is that?)
• A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

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)