Square-free graphs with no six-vertex induced path

2018/05/14 by T. Karthick, Frédéric Maffray, Karthick, T. +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1805.05007

Abstract

We elucidate the structure of (P₆,C₄)-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₆,C₄)-free graph G, \lceil(5ω(G))/(4)\rceil and \lceil(Δ(G) + ω(G) +1)/(2)\rceil are tight upper bounds for the chromatic number of G. Moreover, our structural results imply that every (P₆,C₄)-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₆,C₄)-free graph.

Cited by

• Optimal coloring of \cap,even hole\-free graphs with no short odd holes

Related

• Linearly χ-Bounding (P₆,C₄)-Free Graphs
• Colouring graphs with no induced six-vertex path or diamond
• Coloring (P₆, diamond, K₄)-free graphs
• On the structure of (4K₁, C₄, P₆)-free graphs
• The chromatic number of (P₅, HVN )-free graphs