Structural domination and coloring of some ( P₇ , C₇)-free graphs

DOI10.1016/J.DISC.2020.112244MaRDI QIDQ2222949zbMATH OpenOpenAlexFDO

Authors T. Karthick, Manoj M. Belavadi, S. A. Choudum

Publication date 27 January 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.05018

zbMATH Keywords

\( P_7\)-free graphschromatic numberclique numbersplit graphsstructural domination

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: 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 $calC$-free, where $calC$ is a set of six graphs which includes $P_7$ and $C_7$, and each containing an induced $P_5$. A similar characterisation is shown for the class of graphs which are dominated by induced complete split graphs. Motivated by these results, we study structural descriptions of some classes of $calC$-free graphs. In particular, we give structural descriptions for the class of ($P_7$,$C_7$,$C_4$,gem)-free graphs and for the class of ($P_7$,$C_7$,$C_4$,diamond)-free graphs. Using these results, we show that every ($P_7$,$C_7$,$C_4$,gem)-free graph $G$ satisfies $chi(G)leq2omega(G)-1$, and that every ($P_7$,$C_7$,$C_4$,diamond)-free graph $H$ satisfies $chi(H)leqomega(H)+1$. These two upper bounds are tight for any subgraph of the Petersen graph containing a $C_5$.

Recommendations

• The class of \((P_7, C_4, C_5)\)-free graphs: decomposition, algorithms, and \(\chi \)-boundedness
• Dominating subgraphs in graphs with some forbidden structures
• A New Characterization of P_k-free Graphs
• A new characterization of P_k-free graphs
• On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs

Cites work

• A new characterization of \(P_{6}\)-free graphs
• Characterization of graphs dominated by induced paths
• Clustering and domination in perfect graphs
• Coloring the hypergraph of maximal cliques of a graph with no long path
• Complete description of forbidden subgraphs in the structural domination problem
• Dominating Bipartite Subgraphs in Graphs
• Dominating cliques in \(P_ 5\)-free graphs
• Dominating cliques in graphs
• Dominating sets for split and bipartite graphs
• Domination properties and induced subgraphs
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• Perfect coloring and linearly χ-boundP6-free graphs
• Perfect divisibility and 2‐divisibility
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Square-Free Graphs with No Six-Vertex Induced Path
• The class of \((P_7, C_4, C_5)\)-free graphs: decomposition, algorithms, and \(\chi \)-boundedness
• The Comparability Graph of a Tree
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices

Cited in

(8)

• A new characterization of P_k-free graphs
• The class of \((P_7, C_4, C_5)\)-free graphs: decomposition, algorithms, and \(\chi \)-boundedness
• The structure and the number of \(P_7\)-free bipartite graphs
• Structure of some ( P₇, C₄)-free graphs with application to colorings
• Structure and coloring of a family of (P₇, C₅)-free graphs
• Structure and coloring of (P₇, C₅, diamond)-free graphs
• Coloring of \((P_6, \mathrm{dart}, K_4)\)-free graphs
• Nearly optimal coloring of some C₄-free graphs

This page was built for publication: Structural domination and coloring of some \(( P_7 , C_7)\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2222949)