Square-Free Graphs with No Six-Vertex Induced Path

DOI10.1137/18M1190653zbMATH Open1421.05044arXiv1805.05007OpenAlexW2963915939WikidataQ127838587 ScholiaQ127838587MaRDI QIDQ5232134FDOQ5232134

Authors: T. Karthick, Frédéric Maffray 

Publication date: 29 August 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We elucidate the structure of $(P_6,C_4)$-free graphs by showing that every such graph either has a clique cutset, or a universal vertex, or belongs to several special classes of graphs. Using this result, we show that for any $(P_6,C_4)$-free graph $G$, $lceilfrac5omega(G)4ceil$ and $lceilfracDelta(G)+omega(G)+12ceil$ are tight upper bounds for the chromatic number of $G$. Moreover, our structural results imply that every ($P_6$,$C_4$)-free graph with no clique cutset has bounded clique-width, and thus the existence of a polynomial-time algorithm that computes the chromatic number (or stability number) of any $(P_6,C_4)$-free graph.

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

Recommendations

• Triangle-free graphs with no six-vertex induced path
• Square-free graphs with no induced fork
• Colouring graphs with no induced six-vertex path or diamond
• Colouring graphs with no induced six-vertex path or diamond
• Colouring square-free graphs without long induced paths
• Colouring square-free graphs without long induced paths
• On a class of square-free graphs
• Triangle-free graphs with six non-zero eigenvalues
• The Triangle-Free Graphs with Rank 6
• Graphs with No Induced Five‐Vertex Path or Antipath

zbMATH Keywords

chromatic numberdegree\(\chi\)-boundedness\(P_6\)-free graphsclique sizesquare-free graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Cites Work

• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Title not available (Why is that?)
• Algorithmic graph theory and perfect graphs
• Handle-rewriting hypergraph grammars
• A characterization of perfect graphs
• Title not available (Why is that?)
• Trivially perfect graphs
• Title not available (Why is that?)
• A Note On Reed's Conjecture
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• Stable sets in certain \(P_6\)-free graphs
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• New graph classes of bounded clique-width
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Perfect coloring and linearly χ-boundP6-free graphs
• Radius two trees specify χ‐bounded classes
• Radius Three Trees in Graphs with Large Chromatic Number
• Coloring the hypergraph of maximal cliques of a graph with no long path
• Edge dominating set and colorings on graphs with fixed clique-width
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• Coloring quasi-line graphs
• Claw-free graphs. VI: Colouring
• A description of claw-free perfect graphs
• Substitution and \(\chi\)-boundedness
• Bisimplicial vertices in even-hole-free graphs
• Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs
• Linearly \(\chi\)-bounding \((P_6,C_4)\)-free graphs
• On the structure of (pan, even hole)‐free graphs
• Colouring square-free graphs without long induced paths.
• Coloring (gem, co‐gem)‐free graphs
• Square-Free Graphs with No Six-Vertex Induced Path
• Bounding the Clique‐Width of H‐Free Chordal Graphs

Cited In (17)

• Graphs with No Induced Five‐Vertex Path or Antipath
• On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs
• A BOUND FOR THE CHROMATIC NUMBER OF (, GEM)-FREE GRAPHS
• Optimal chromatic bound for (P2+P3,P2+P3¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graphs
• Coloring of \((P_5, 4\)-wheel)-free graphs
• Structural domination and coloring of some \(( P_7 , C_7)\)-free graphs
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Graphs obtained by disjoint unions and joins of cliques and stable sets
• Colouring graphs with no induced six-vertex path or diamond
• Colouring graphs with no induced six-vertex path or diamond
• Colouring square-free graphs without long induced paths
• Structure of some \(( P_7, C_4)\)-free graphs with application to colorings
• Coloring (\(P_5\), kite)-free graphs with small cliques
• THE CHROMATIC NUMBER OF -FREE GRAPHS
• An optimal χ‐bound for (P6, diamond)‐free graphs
• Square-Free Graphs with No Six-Vertex Induced Path
• Coloring graphs with no induced five‐vertex path or gem

This page was built for publication: Square-Free Graphs with No Six-Vertex Induced Path

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