On the Chromatic Number of Some (P3 ∨ P2)-Free Graphs

Article Mathematics, Applied

Bounds for the chromatic number of some pK2-free graphs

Athmakoori Prashant et al.

Summary: The paper focuses on the concept of chi-binding functions for 2K(2)-free graphs and improves the existing function for {2K(2), K-1 + C-4}free graphs. It also introduces a linear chi-binding function for {2K(2), K-2 + P-4}-free graphs. Additionally, alternative proofs are provided for the chi-binding functions of {2K(2), gem}-free graphs, {2K(2), HVN}-free graphs, and {2K(2), K-5 - e}-free graphs. Finally, polynomial chi-binding functions are found for {pK(2), H}-free graphs where H is an element of{gem, diamond, K-2+ P4, HVN, K-5 - e, butterfly, gem(+), dart, K-1 + C4, C4, (P5) over bar} when p >= 2.

DISCRETE APPLIED MATHEMATICS (2023)

Add to Collection

Article Mathematics

Coloring of Some Crown-Free Graphs

Di Wu et al.

GRAPHS AND COMBINATORICS (2023)

Add to Collection

Article Mathematics

The ?-Boundedness of (P2?P3)-Free Graphs

Xiao Wang et al.

Summary: In this paper, the concept of chi-binding and chi-binding functions are introduced to extend the notion of perfectness. Challenging conjectures about the chi-bound are discussed. By analyzing triangle-free graphs and specific types of graphs, several conclusions about the chromatic number and maximum degree of a graph are derived through proofs and deductions.

JOURNAL OF MATHEMATICS (2022)

Add to Collection

Article Mathematics, Applied

Homogeneous sets, clique-separators, critical graphs, and optimal X -binding functions

Christoph Brause et al.

Summary: In this paper, the optimal chi-binding functions for subclasses of P-5-free graphs and (C-5, C-7, ...)-free graphs are determined using a combination of decomposition methods. Several conclusions are derived, including the verification of Reed's conjecture for (P-5, banner)-free graphs.

DISCRETE APPLIED MATHEMATICS (2022)

Add to Collection

Article Mathematics

An optimal χ-bound for ( P 6, diamond)-free graphs

Kathie Cameron et al.

Summary: In this paper, it is shown that for every (P6, diamond)-free graph G, the chromatic number chi (G) is less than or equal to the clique number omega (G) plus 3. The bound is achieved by the complement of the 27-vertex Schlafli graph. The proof is based on a reduction to imperfect (P6, diamond)-free graphs, analysis of their structure, and a computer search relying on a characterization of 3-colorable (P6, K3)-free graphs.

JOURNAL OF GRAPH THEORY (2021)

Add to Collection

Article Mathematics