Browsing Combinatorics and Optimization by Subject "χ-Boundedness"
Now showing items 1-1 of 1
-
A Counterexample to a Conjecture About Triangle-Free Induced Subgraphs of Graphs with Large Chromatic Number
(Elsevier ScienceDirect, 2023-01)We prove that for every n, there is a graph G with χ(G) ≥ n and ω(G) ≤ 3 such that every induced subgraph H of G with ω(H) ≤ 2 satisfies χ(H) ≤ 4.This disproves a well-known conjecture. Our construction is a digraph with ...