Chromatic number of ISK4-free graphs

2016/11/14 by Le, Ngoc Khang
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1611.04279

Abstract

A graph G is said to be ISK4-free if it does not contain any subdivision of K₄ as an induced subgraph. In this paper, we propose new upper bounds for chromatic number of ISK4-free graphs and \ISK4, triangle\-free graphs.

Related

• Square-free graphs with no six-vertex induced path
• Tight Chromatic Upper Bound for 3K1, K1+C4-free Graphs
• A Note Related to Graph Theory
• On minimal triangle-free 6-chromatic graphs
• (P₂+P₄, K₄-e)-free graphs are nearly ω-colorable