Towards Optimal ?-Binding Functions of (2K1?K2)-Free Graphs and (P3?K1)-Free Graphs

Title

Towards Optimal ?-Binding Functions of (2K1?K2)-Free Graphs and (P3?K1)-Free Graphs

Creator

Angeliya, C.U.; Choudum, Sheshayya; Joseph, Mayamma

Description

A function f:N?R is called a ?-binding function for a hereditary family G of graphs, if ?(G)?f(?(G)) for every G?G where ?(G) and ?(G) denote the chromatic number and clique number respectively. In his influential work, Gya?fa? (1987) showed that the family of (2K1?K2)-free graphs and the family of (P3?K1)-free graphs are ?-bounded. Randerath and Schiermeyer (2004) improved the ?-binding functions of both these classes to x+12. In this paper, we further improve the ?-binding function of both these classes to x22 for x?3. Furthermore, we obtain a tight chromatic bound for (P3?K1)-free graphs with clique number 4. The Author(s), under exclusive licence to Springer Nature Japan KK 2025.

Source

Graphs and Combinatorics;Volume;41;Issue;2;Article No.;39;

Date

01-01-2025

Publisher

Springer

Subject

(2K₁?K₂)-free graphs; (P₃?K₁)-free graphs; Chromatic number; Clique number; ?-binding function

Coverage

Angeliya C.U., Department of Mathematics, Christ University, Bangalore, 560029, India; Choudum S., Department of Mathematics, Christ University, Bangalore, 560029, India; Joseph M., Department of Mathematics, Christ University, Bangalore, 560029, India

Rights

Restricted Access; Hardcopy may be available in the library

Relation

ISSN: 9110119;

Format

online

Language

English

Type

Article

Identifier

https://doi.org/10.1007/s00373-025-02897-7

https://www.scopus.com/pages/publications/85218683073?origin=resultslist