Homogeneous sets, clique-separators, critical graphs, and optimal χ -binding functions
2022; Elsevier BV; Volume: 320; Linguagem: Inglês
10.1016/j.dam.2022.05.014
ISSN1872-6771
AutoresChristoph Brause, Maximilian Geißer, Ingo Schiermeyer,
Tópico(s)Graph theory and applications
ResumoGiven a set H of graphs, let fH⋆:N>0→N>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}⋆(ω)=f{3K1}⋆(ω)∈Θ(ω2/log(ω)), (ii) f{P5,co-banner}⋆(ω)=f{2K2}⋆(ω)∈O(ω2), (iii) f{C5,C7,…,banner}⋆(ω)=f{C5,3K1}⋆(ω)∉O(ω), and. (iv) f{P5,C4}⋆(ω)=⌈(5ω−1)/4⌉. 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, Reed's conjecture – relating chromatic number, clique number, and maximum degree of a graph – follows for (P5,banner)-free graphs.
Referência(s)