Square-free graphs with no induced fork
type: Item
instance of: scholarly article
title: Square-free graphs with no induced fork
zbMATH Open document ID: 1464.05146
DOI: 10.37236/9144
author: Maria Chudnovsky
author: Shenwei Huang
author: T. Karthick
author: Jenny Kaufmann
published in: The Electronic Journal of Combinatorics
publication date: 2021-05-11T00:00:00Z
review text: Summary: The claw is the graph \(K_{1,3}\), and the fork is the graph obtained from the claw \(K_{1,3}\) by subdividing one of its edges once. In this paper, we prove a structure theorem for the class of (claw, \(C_4)\)-free graphs that are not quasi-line graphs, and a structure theorem for the class of (fork, \(C_4)\)-free graphs that uses the class of (claw, \(C_4)\)-free graphs as a basic class. Finally, we show that every (fork, \(C_4\))-free graph \(G\) satisfies \(\chi(G)\leqslant \bigg\lceil\frac{3\omega(G)}{2}\bigg\rceil\) via these structure theorems with some additional work on coloring basic classes.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 7347104
zbMATH Keywords: forbidden induced subgraph
zbMATH Keywords: graph structure
zbMATH Keywords: fork
zbMATH Keywords: antifork
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.37236/9144
OpenAlex ID: W3157320200
cites work: On the chromatic number of \(2 K_2\)-free graphs
cites work: Excluding the fork and antifork
cites work: Coloring quasi-line graphs
cites work: Q3416248
cites work: Claw-free graphs. VI: Colouring
cites work: Q5749319
cites work: Radius two trees specify χ‐bounded classes
cites work: The Ramsey number R(3, t) has order of magnitude t2/log t
cites work: Sur le coloriage des graphs
cites work: Vertex colouring and forbidden subgraphs -- a survey
cites work: Q3932997
description: scientific article; zbMATH DE number 7347104