2020/05/05 by Christoph Brause, Brause, Christoph, Maximilian Geißer +3 · 3 citations
Mathematics · Computer Science · Medicine · #Graph theory and applications #Advanced Graph Theory Research #Metal complexes synthesis and properties
paper · pdf · doi:10.48550/arxiv.2005.02250
Given a set H of graphs, let fH^⋆\colon ℕ>0→ ℕ>0 be the optimal χ-binding function of the class of H-free graphs, that is, fH^⋆(ω)=max\χ(G): G is H-free, ω(G)=ω\. In this paper, we combine the two decomposition methods by homogeneous sets and clique-separators in order to determine optimal χ-binding functions for subclasses of P5-free graphs and of (C5,C7,…)-free graphs. In particular, we prove the following for each ω≥ 1: (i) f_\P5,banner\^⋆(ω)=f3K1^⋆(ω)∈ Θ(ω2/log(ω)), (ii) f_\P5,co-banner\^⋆(ω)=f^⋆_\2K2\(ω)\inO(ω2), (iii) f_\C5,C7,…,banner\^⋆(ω)=f^⋆_\C5,3K1\(ω)∉ O(ω), and (iv) f_\P5,C4\^⋆(ω)=\lceil(5ω-1)/4\rceil. We also characterise, for each of our considered graph classes, all graphs G with χ(G)>χ(G-u) for each u∈ V(G). From these structural results, we can prove Reed's conjecture -- relating chromatic number, clique number, and maximum degree of a graph -- for (P5,banner)-free graphs.