Triangle-free graphs and forbidden subgraphs

DOI10.1016/S0166-218X(01)00277-3zbMath1003.05039OpenAlexW2066158472MaRDI QIDQ1613361

Stephan Brandt

Publication date: 29 August 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00277-3

zbMATH Keywords

chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (15)

Chromatic bounds for the subclasses of \(pK_2\)-free graphs ⋮ \(P_3\)-hull number of graphs with diameter two ⋮ On the chromatic number of (\(P_6\), diamond)-free graphs ⋮ Improved bounds on the chromatic number of (\(P_5\), flag)-free graphs ⋮ Bounds for the chromatic number of some \(pK_2\)-free graphs ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time ⋮ Coloring (\(P_5\), kite)-free graphs with small cliques ⋮ Coloring graphs without short cycles and long induced paths ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree ⋮ Colouring Vertices of Triangle-Free Graphs ⋮ Coloring Graphs without Short Cycles and Long Induced Paths ⋮ Colouring vertices of triangle-free graphs without forests

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The core of a graph
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• A bound on the chromatic number of graphs without certain induced subgraphs
• Graphs whose every independent set has a common neighbour
• Dominating subgraphs in graphs with some forbidden structures
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• On a property of the class of n-colorable graphs
• Graph Theory and Probability
• Über ein Extremalproblem der Graphentheorie
• Graph Classes: A Survey
• On the Structure of Dense Triangle-Free Graphs
• Radius two trees specify χ‐bounded classes
• The Ramsey number R(3, t) has order of magnitude t²/log t

This page was built for publication: Triangle-free graphs and forbidden subgraphs