A survey of χ‐boundedness
From MaRDI portal
Publication:5066934
DOI10.1002/jgt.22601zbMath1486.05102arXiv1812.07500OpenAlexW3080973359MaRDI QIDQ5066934
Alexander D. Scott, P. D. Seymour
Publication date: 31 March 2022
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1812.07500
Related Items (67)
Local boxicity ⋮ Improved bounds for colouring circle graphs ⋮ Chordal directed graphs are not \(\chi\)-bounded ⋮ Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs ⋮ Graph theory -- a survey on the occasion of the Abel Prize for László Lovász ⋮ On the chromatic number of some \(P_5\)-free graphs ⋮ 2-divisibility of some odd hole free graphs ⋮ Coloring graph classes with no induced fork via perfect divisibility ⋮ Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor ⋮ Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree ⋮ THE CHROMATIC NUMBER OF -FREE GRAPHS ⋮ Triangle‐free graphs with large chromatic number and no induced wheel ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Polynomial bounds for chromatic number II: Excluding a star‐forest ⋮ Polynomial bounds for chromatic number. III. Excluding a double star ⋮ Coloring of some crown-free graphs ⋮ Some remarks on graphs with no induced subdivision of \(K_4\) ⋮ On coloring digraphs with forbidden induced subgraphs ⋮ Attempting perfect hypergraphs ⋮ An optimal χ‐bound for (P6, diamond)‐free graphs ⋮ Polynomial bounds for chromatic number VII. Disjoint holes ⋮ Rainbow independent sets in certain classes of graphs ⋮ Coloring graphs without induced \(P_5\) or \(K_5-e\) ⋮ Problems close to my heart ⋮ Weakening total coloring conjecture and Hadwiger's conjecture on total graphs ⋮ A note on the Gyárfás-Sumner conjecture ⋮ Highly Connected Subgraphs with Large Chromatic Number ⋮ Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded ⋮ Optimal chromatic bound for (P2+P3,P2+P3¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graphs ⋮ Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors ⋮ Disjointness graphs of short polygonal chains ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Polynomial bounds for chromatic number. V: Excluding a tree of radius two and a complete multipartite graph ⋮ Burling graphs revisited. II: Structure ⋮ Burling graphs revisited. III: Applications to \(\chi \)-boundedness ⋮ Borodin-Kostochka conjecture holds for odd-hole-free graphs ⋮ Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022 ⋮ Towards the Chen-Raspaud conjecture ⋮ Coloring triangle-free L-graphs with \(O (\log \log n)\) colors ⋮ Hitting all maximum stable sets in \(P_5\)-free graphs ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ Near optimal colourability on hereditary graph families ⋮ Graphs of large chromatic number ⋮ Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of \(P_4\) ⋮ Odd distances in colourings of the plane ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Burling graphs revisited. I: New characterizations ⋮ Polynomial bounds for chromatic number VI. Adding a four-vertex path ⋮ A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs ⋮ A better upper bound on the chromatic number of (cap, even-hole)-free graphs ⋮ Box and Segment Intersection Graphs with Large Girth and Chromatic Number ⋮ Classes of graphs with no long cycle as a vertex-minor are polynomially \(\chi\)-bounded ⋮ Structure and colour in triangle-free graphs ⋮ Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Dense Induced Subgraphs of Dense Bipartite Graphs ⋮ Circle graphs are quadratically χ‐bounded ⋮ From \(\chi\)- to \(\chi_p\)-bounded classes ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number ⋮ Helly-type problems ⋮ A note on a conjecture of Wu, Xu and Xu ⋮ Coloring of \((P_5, 4\)-wheel)-free graphs
This page was built for publication: A survey of χ‐boundedness
