Square-free graphs with no induced fork

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

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume28
Issue number2
DOIs
StatePublished - 2021

All Science Journal Classification (ASJC) codes

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

Fingerprint

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

Cite this