Square-Free Graphs with No Six-Vertex Induced Path

DOI10.1137/18M1190653zbMath1421.05044arXiv1805.05007OpenAlexW2963915939WikidataQ127838587 ScholiaQ127838587MaRDI QIDQ5232134

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

degreechromatic number\(\chi\)-boundedness\(P_6\)-free graphsclique sizesquare-free graphs

Mathematics Subject Classification ID

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

Related Items (13)

Colouring graphs with no induced six-vertex path or diamond ⋮ THE CHROMATIC NUMBER OF -FREE GRAPHS ⋮ An optimal χ‐bound for (P6, diamond)‐free graphs ⋮ Coloring graphs with no induced five‐vertex path or gem ⋮ Optimal chromatic bound for (P2+P3,P2+P3¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graphs ⋮ Coloring (\(P_5\), kite)-free graphs with small cliques ⋮ Structural domination and coloring of some \(( P_7 , C_7)\)-free graphs ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ Square-Free Graphs with No Six-Vertex Induced Path ⋮ Colouring graphs with no induced six-vertex path or diamond ⋮ A BOUND FOR THE CHROMATIC NUMBER OF (, GEM)-FREE GRAPHS ⋮ Colouring square-free graphs without long induced paths ⋮ Coloring of \((P_5, 4\)-wheel)-free graphs

Cites Work

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

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