Browsing Combinatorics and Optimization by Author "Moore, Benjamin"
Now showing items 1-3 of 3
-
A Counterexample to a Conjecture About Triangle-Free Induced Subgraphs of Graphs with Large Chromatic Number
Carbonero, Alvaro; Hompe, Patrick; Moore, Benjamin; Spirkl, Sophie (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 ... -
Digraphs with All Induced Directed Cycles of the Same Length are not → χ -Bounded
Carbonero, Alvaro; Hompe, Patrick; Moore, Benjamin; Spirkl, Sophie (2022-10-07)For t > 2, let us call a digraph D t-chordal if all induced directed cycles in D have length equal to t. In an earlier paper, we asked for which t it is true that t-chordal graphs with bounded clique number have bounded ... -
Fractional refinements of integral theorems
Moore, Benjamin (University of Waterloo, 2021-07-09)The focus of this thesis is to take theorems which deal with ``integral" objects in graph theory and consider fractional refinements of them to gain additional structure. A classic theorem of Hakimi says that for an ...