Induced subtrees in graphs of large chromatic number

From MaRDI portal
Publication:1159679

DOI10.1016/0012-365X(80)90230-7zbMath0475.05027OpenAlexW2050675734MaRDI QIDQ1159679

Endre Szemerédi, Zsolt Tuza, András Gyárfás

Publication date: 1980

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

Full work available at URL: https://doi.org/10.1016/0012-365x(80)90230-7



Related Items

Induced subgraphs of graphs with large chromatic number. XI. Orientations, Induced subgraphs of graphs with large chromatic number. I. Odd holes, Radius two trees specify χ‐bounded classes, Applications of hypergraph coloring to coloring graphs not inducing certain trees, Classes of graphs that exclude a tree and a clique and are not vertex Ramsey, The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices, A note on chromatic number and induced odd cycles, Radius two trees specify χ‐bounded classes, Trees in greedy colorings of hypergraphs, Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree, Polynomial bounds for chromatic number II: Excluding a star‐forest, Polynomial bounds for chromatic number. III. Excluding a double star, Chromatic number and subtrees of graphs, A note on the Gyárfás-Sumner conjecture, Polynomial bounds for chromatic number. V: Excluding a tree of radius two and a complete multipartite graph, Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs, A Ramsey–Turán theory for tilings in graphs, Graphs of large chromatic number, Characterization of forbidden subgraphs for bounded star chromatic number, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, Packing trees into \(n\)-chromatic graphs, On the combinatorial problems which I would most like to see solved, Substitution and \(\chi\)-boundedness, Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey, Induced colorful trees and paths in large chromatic graphs, Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree, Colorful induced subgraphs, First-fit coloring of bounded tolerance graphs, Induced subgraphs of graphs with large chromatic number. XIII. New brooms, On lower bounds for the chromatic number in terms of vertex degree, On induced colourful paths in triangle-free graphs, Structure and colour in triangle-free graphs, Large induced trees in \(K_r\)-free graphs, Induced cycles and chromatic number



Cites Work