Graphs with _1 and _1 both large

DOI10.1007/S00373-018-1902-ZMaRDI QIDQ2413631zbMATH OpenOpenAlexFDO

Authors Gregory J. Puleo

Publication date 14 September 2018

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

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

zbMATH Keywords

triangleindependencecoveringtriangular graph

Mathematics Subject Classification ID

Distance in graphs (05C12)

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

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

Cites work

• scientific article; zbMATH DE number 4213989 (Why is no real title available?)
• scientific article; zbMATH DE number 3914370 (Why is no real title available?)
• scientific article; zbMATH DE number 3914371 (Why is no real title available?)
• Covering and independence in triangle structures
• Maximal \(k\)-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture
• On a conjecture of Fink and Jacobson concerning k-domination and k- dependence
• The Ramsey number R(3, t) has order of magnitude t²/log t
• \(k\)-domination and \(k\)-independence in graphs: A survey

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)