Square-Free Graphs with No Six-Vertex Induced Path

DOI10.1137/18M1190653MaRDI QIDQ5232134zbMATH OpenOpenAlexWikidataFDO

Authors T. Karthick, Frédéric Maffray

Publication date 29 August 2019

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

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

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)

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.

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

Cites work

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

Cited in

(21)

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

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)