Graphs with _1 and _1 both large

DOI10.1007/S00373-018-1902-ZzbMATH Open1395.05052arXiv1705.04745OpenAlexW2801097450MaRDI QIDQ2413631FDOQ2413631

Authors: Gregory J. Puleo 

Publication date: 14 September 2018

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: Given a graph $G$, let $a{u}_1(G)$ denote the smallest size of a set of edges whose deletion makes $G$ triangle-free, and let $alph{a}_1(G)$ denote the largest size of an edge set containing at most one edge from each triangle of $G$. ErdH{o}s, Gallai, and Tuza introduced several problems with the unifying theme that $alph{a}_1(G)$ and $a{u}_1(G)$ cannot both be "very large"; the most well-known such problem is their conjecture that $alph{a}_1(G)+a{u}_1(G)leq|V(G){|}^2/4$, which was proved by Norin and Sun. We consider three other problems within this theme (two introduced by ErdH{o}s, Gallai, and Tuza, another by Norin and Sun), all of which request an upper bound either on $minalph{a}_1(G),a{u}_1(G)$ or on $alph{a}_1(G)+ka{u}_1(G)$ for some constant $k$, and prove the existence of graphs for which these quantities are "large".

Full work available at URL: https://arxiv.org/abs/1705.04745

Recommendations

• extremal aspects of the Erdős-Gallai-Tuza conjecture
• Covering and independence in triangle structures
• On a Conjecture of Erdős, Gallai, and Tuza
• A note on bipartite subgraphs and triangle-independent sets
• A conjecture on triangles of graphs

zbMATH Keywords

triangleindependencecoveringtriangular graph

Mathematics Subject Classification ID

Distance in graphs (05C12)

Cites Work

• On a conjecture of Fink and Jacobson concerning k-domination and k- dependence
• Title not available (Why is that?)
• \(k\)-domination and \(k\)-independence in graphs: A survey
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Title not available (Why is that?)
• Title not available (Why is that?)
• Maximal \(k\)-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture
• Covering and independence in triangle structures

Cited In (1)

• Covering the edges of a graph with triangles

This page was built for publication: Graphs with \(\alpha _1\) and \(\tau _1\) both large

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2413631)