Structural domination and coloring of some (P7,C7)-free graphs

Title

Structural domination and coloring of some (P7,C7)-free graphs

Creator

Choudum S.A.; Karthick T.; Belavadi M.M.

Description

We show that every connected induced subgraph of a graph G is dominated by an induced connected split graph if and only if G is C-free, where C is a set of six graphs which includes P7 and C7, and each containing an induced P5. A similar characterization is shown for the class of graphs which are dominated by an induced connected complete split graph. Motivated by these results, we study structural descriptions of some classes of (P7, C7)-free graphs. In particular, we give structural descriptions for the class of (P7, C7, C4, gem)-free graphs and for the class of (P7, C7, C4, diamond)-free graphs. Using these results, we show that every (P7, C7, C4, gem)-free graph G satisfies ?(G)?2?(G)?1, and that every (P7, C7, C4, diamond)-free graph H satisfies ?(H)?max{3,?(H)}. 2020 Elsevier B.V.

Source

Discrete Mathematics, Vol-344, No. 3

Date

2021-01-01

Publisher

Elsevier B.V.

Subject

Chromatic number; Clique number; P₇-free graphs; Split graphs; Structural domination

Coverage

Choudum S.A., Department of Mathematics, CHRIST (Deemed to be University), Bengaluru, 560029, India; Karthick T., Computer Science Unit, Indian Statistical Institute, Chennai Centre, Chennai, 600029, India; Belavadi M.M., Department of Mathematics, CHRIST (Deemed to be University), Bengaluru, 560029, India

Rights

Restricted Access

Relation

ISSN: 0012365X; CODEN: DSMHA

Format

Online

Language

English

Type

Article

Identifier

https://doi.org/10.1016/j.disc.2020.112244

https://www.scopus.com/inward/record.uri?eid=2-s2.0-85097379588&doi=10.1016%2fj.disc.2020.112244&partnerID=40&md5=719fe0d0ac0258211afcdc3c75705790