On Line Graphs of Subcubic Triangle-Free Graphs

Andrea Munaro

doi:10.1016/j.disc.2017.01.006

On Line Graphs of Subcubic Triangle-Free Graphs

Andrea Munaro

School of Mathematics and Physics

Research output: Contribution to journal › Article › peer-review

20 Citations (Scopus)

225 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 language	English
Pages (from-to)	1210-1226
Number of pages	17
Journal	Discrete Mathematics
Volume	340
Issue number	6
DOIs	https://doi.org/10.1016/j.disc.2017.01.006
Publication status	Published - 27 Feb 2017

Keywords

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

Access to Document

10.1016/j.disc.2017.01.006Licence: Unspecified

On Line Graphs of Subcubic Triangle-Free Graphs
© 2019 Elsevier Ltd. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/,which permits distribution and reproduction for non-commercial purposes, provided the author and source are cited.
Licence: CC BY-NC-ND

Cite this

@article{aa6963d559e64d92a9d6d89d4374396c,

title = "On Line Graphs of Subcubic Triangle-Free Graphs",

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{\textquoteright} 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.",

keywords = "Approximation hardness, Independence number, Line graph, Matching number, Min-max theorems, NP-completeness",

author = "Andrea Munaro",

year = "2017",

month = feb,

day = "27",

doi = "10.1016/j.disc.2017.01.006",

language = "English",

volume = "340",

pages = "1210--1226",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - On Line Graphs of Subcubic Triangle-Free Graphs

AU - Munaro, Andrea

PY - 2017/2/27

Y1 - 2017/2/27

N2 - 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.

AB - 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.

KW - Approximation hardness

KW - Independence number

KW - Line graph

KW - Matching number

KW - Min-max theorems

KW - NP-completeness

UR - http://www.mendeley.com/research/line-graphs-subcubic-trianglefree-graphs

U2 - 10.1016/j.disc.2017.01.006

DO - 10.1016/j.disc.2017.01.006

M3 - Article

SN - 0012-365X

VL - 340

SP - 1210

EP - 1226

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 6

ER -

On Line Graphs of Subcubic Triangle-Free Graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this