Square-free graphs with no induced fork

Maria Chudnovsky, Shenwei Huang, T. Karthick, Jenny Kaufmann

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


The claw is the graph K1,3, and the fork is the graph obtained from the claw K1,3 by subdividing one of its edges once. In this paper, we prove a structure theorem for the class of (claw, C4)-free graphs that are not quasi-line graphs, and a structure theorem for the class of (fork, C4)-free graphs that uses the class of (claw, C4)-free graphs as a basic class. Finally, we show that every (fork, C4)-free graph G satisfies (formula presented) via these structure theorems with some additional work on coloring basic classes.

Original languageEnglish (US)
Article number#P2.20
JournalElectronic Journal of Combinatorics
Issue number2
StatePublished - 2021

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Square-free graphs with no induced fork'. Together they form a unique fingerprint.

Cite this