On Line Graphs of Subcubic Triangle-Free Graphs

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)
83 Downloads (Pure)

Abstract

Line graphs constitute a rich and well-studied class of graphs. In this paper, we focus on three different topics related to line graphs of subcubic triangle-free graphs. First, we show that any such graph has an independent set of size at least , the bound being sharp. As an immediate consequence, we have that any subcubic triangle-free graph , with vertices of degree , has a matching of size at least . Then we provide several approximate min-max theorems relating cycle-transversals and cycle-packings of line graphs of subcubic triangle-free graphs. This enables us to prove Jones’ Conjecture for claw-free graphs with maximum degree . Finally, we concentrate on the computational complexity of Feedback Vertex Set, Hamiltonian Cycle and Hamiltonian Path for subclasses of line graphs of subcubic triangle-free graphs.
Original languageEnglish
Pages (from-to)1210-1226
Number of pages17
JournalDiscrete Mathematics
Volume340
Issue number6
DOIs
Publication statusPublished - 27 Feb 2017

Keywords

  • Approximation hardness
  • Independence number
  • Line graph
  • Matching number
  • Min-max theorems
  • NP-completeness

Fingerprint Dive into the research topics of 'On Line Graphs of Subcubic Triangle-Free Graphs'. Together they form a unique fingerprint.

Cite this