Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
On Tuza's conjecture in even co-chain graphs
View through CrossRef
In 1981, Tuza conjectured that the cardinality of a minimum set of edges that intersects every triangle of a graph is at most twice the cardinality of a maximum set of edge-disjoint triangles. This conjecture has been proved for several important graph classes, as planar graphs, tripartite graphs, among others. However, it remains open on other important classes of graphs, as chordal graphs. Furthermore, it remains open for main subclasses of chordal graphs, as split graphs and interval graphs. In this paper, we show that Tuza’s conjecture is valid for even co-chain graphs, a known subclass of interval graphs.
Sociedade Brasileira de Computação - SBC
Title: On Tuza's conjecture in even co-chain graphs
Description:
In 1981, Tuza conjectured that the cardinality of a minimum set of edges that intersects every triangle of a graph is at most twice the cardinality of a maximum set of edge-disjoint triangles.
This conjecture has been proved for several important graph classes, as planar graphs, tripartite graphs, among others.
However, it remains open on other important classes of graphs, as chordal graphs.
Furthermore, it remains open for main subclasses of chordal graphs, as split graphs and interval graphs.
In this paper, we show that Tuza’s conjecture is valid for even co-chain graphs, a known subclass of interval graphs.
Related Results
The Galois Brumer–Stark conjecture for SL2(????3)-extensions
The Galois Brumer–Stark conjecture for SL2(????3)-extensions
In a previous work, we stated a conjecture, called the Galois Brumer–Stark conjecture, that generalizes the (abelian) Brumer–Stark conjecture to Galois extensions. We also proved t...
The Complexity of Mathematics
The Complexity of Mathematics
The strong Goldbach's conjecture states that every even integer greater than 2 can be written as the sum of two primes. The conjecture that all odd numbers greater than 7 are the s...
On aspherical presentations of groups
On aspherical presentations of groups
The Whitehead asphericity conjecture claims that if
⟨
A
‖
R
⟩
\langle \...
How artificial intelligence-based supply chain analytics enable supply chain agility and innovation? An intellectual capital perspective
How artificial intelligence-based supply chain analytics enable supply chain agility and innovation? An intellectual capital perspective
Purpose
This study aims to empirically examine the impact of intellectual capital on the adoption of artificial intelligence-based supply chain analytics in manufacturing companies...
Twilight graphs
Twilight graphs
AbstractThis paper deals primarily with countable, simple, connected graphs and the following two conditions which are trivially satisfied if the graphs are finite:(a) there is an ...
Critical Exponents, Colines, and Projective Geometries
Critical Exponents, Colines, and Projective Geometries
In [9, p. 469], Oxley made the following conjecture, which is a geometric analogue of a
conjecture of Lovász (see [1, p. 290]) about complete graphs.Conjecture 1.1.Let G be a rank...
Model-checking ecological state-transition graphs
Model-checking ecological state-transition graphs
AbstractModel-checking is a methodology developed in computer science to automatically assess the dynamics of discrete systems, by checking if a system modelled as a state-transiti...
C*-algebraic Bieberbach, Robertson, Lebedev-Milin, Zalcman, Krzyz and Corona Conjectures
C*-algebraic Bieberbach, Robertson, Lebedev-Milin, Zalcman, Krzyz and Corona Conjectures
We study C*-algebraic versions of following conjectures/theorems: (1) Bieberbach conjecture (de Branges theorem) (2) Robertson conjecture (3) Lebedev-Milin conjecture (4) Zalcman c...