On line graphs of subcubic triangle-free graphs

DOI10.1016/J.DISC.2017.01.006zbMath1369.05178OpenAlexW2594362606WikidataQ62721778 ScholiaQ62721778MaRDI QIDQ2400553

Andrea Munaro

Publication date: 29 August 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://pure.qub.ac.uk/en/publications/on-line-graphs-of-subcubic-trianglefree-graphs(aa6963d5-59e6-4d92-a9d6-d89d4374396c).html

zbMATH Keywords

independence numberline graphmatching numberapproximation hardnessmin-max theorems\(\mathsf{NP}\)-completeness

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45) Graph operations (line graphs, products, etc.) (05C76)

Related Items (12)

Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs ⋮ Computing weighted subset transversals in \(H\)-free graphs ⋮ Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs ⋮ Partitioning \(H\)-free graphs of bounded diameter ⋮ Boundary classes for graph problems involving non-local properties ⋮ Feedback vertex set on Hamiltonian graphs ⋮ Classifying subset feedback vertex set for \(H\)-free graphs ⋮ On the price of independence for vertex cover, feedback vertex set and odd cycle transversal ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Computing subset transversals in \(H\)-free graphs ⋮ Independent Feedback Vertex Set for P_5-free Graphs ⋮ On reconfigurability of target sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate min-max relations on plane graphs
• Independent sets in \(\{\text{claw}, K_4 \}\)-free 4-regular graphs
• Independent sets and matchings in subcubic graphs
• Factors and factorizations of graphs. Proof techniques in factor theory
• Independence in graphs with maximum degree four
• On the tightness of the \(\frac {5}{14}\) independence ratio
• Non-Hamiltonian 3-connected cubic bipartite graphs
• Independence, clique size and maximum degree
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• The edge Hamiltonian path problem is NP-complete
• The edge Hamiltonian path problem is NP-complete for bipartite graphs
• Finding independent sets in \(K_4\)-free 4-regular connected graphs
• Gridline graphs: A review in two dimensions and an extension to higher dimensions
• Tight bounds on maximal and maximum matchings
• 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
• Feedback vertex set on planar graphs
• The independence number of connected (claw, \(K_4\))-free 4-regular graphs
• Independent sets in triangle-free cubic planar graphs
• Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree
• On Restrictions of Balanced 2-Interval Graphs
• Spanning even subgraphs of 3‐edge‐connected graphs
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• Some Ramsey-Type Numbers and the Independence Ratio
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• On Independent Circuits Contained in a Graph
• The existence of complete cycles in repeated line-graphs
• On Eulerian and Hamiltonian Graphs and Line Graphs
• On Hamiltonian Line-Graphs
• Characterizations of derived graphs

This page was built for publication: On line graphs of subcubic triangle-free graphs