Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA new class of graphs that satisfies the Chen-Chvatal Conjecture
101
0
0.0
(
0
)
Added by
Pierre Aboulker
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A well-known combinatorial theorem says that a set of n non-collinear points in the plane determines at least n distinct lines. Chen and Chvatal conjectured that this theorem extends to metric spaces, with an appropriated definition of line. In this work we prove a slightly stronger version of Chen and Chvatal conjecture for a family of graphs containing chordal graphs and distance-hereditary graphs.
rate research
Read More
Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average degree, including planar graphs. However, for dense graphs that are neither cliques nor 4-colorable, only asymptotic results are known. Here, we confirm the conjecture for threshold graphs, i.e. graphs that are both split graphs and cographs, and for co-chain graphs with both sides of the same size divisible by 4.
A $k$-linear coloring of a graph $G$ is an edge coloring of $G$ with $k$ colors so that each color class forms a linear forest -- a forest whose each connected component is a path. The linear arboricity $chi_l(G)$ of $G$ is the minimum integer $k$ such that there exists a $k$-linear coloring of $G$. Akiyama, Exoo and Harary conjectured in 1980 that for every graph $G$, $chi_l(G)leq left lceil frac{Delta(G)+1}{2}rightrceil$ where $Delta(G)$ is the maximum degree of $G$. First, we prove the conjecture for 3-degenerate graphs. This establishes the conjecture for graphs of treewidth at most 3 and provides an alternative proof for the conjecture in some classes of graphs like cubic graphs and triangle-free planar graphs for which the conjecture was already known to be true. Next, for every 2-degenerate graph $G$, we show that $chi_l(G)=leftlceilfrac{Delta(G)}{2}rightrceil$ if $Delta(G)geq 5$. We conjecture that this equality holds also when $Delta(G)in{3,4}$ and show that this is the case for some well-known subclasses of 2-degenerate graphs. All our proofs can be converted into linear time algorithms.
A propositional logic sentence in conjunctive normal form that has clauses of length two (a 2-CNF) can be associated with a multigraph in which the vertices correspond to the variables and edges to clauses. We first show that every such sentence that has been reduced, that is, which is unchanged under application of certain tautologies, is equisatisfiable to a 2-CNF whose associated multigraph is, in fact, a simple graph. Our main result is a complete characterization of graphs that can support unsatisfiable 2-CNF sentences. We show that a simple graph can support an unsatisfiable reduced 2-CNF sentence if and only if it contains any one of four specific small graphs as a topological minor. Equivalently, all reduced 2-CNF sentences supported on a given simple graph are satisfiable if and only if all subdivisions of those four graphs are forbidden as subgraphs of of the original graph. We conclude with a discussion of why the Robertson-Seymour graph minor theorem does not apply in our approach.
Tuza (1981) conjectured that the size $tau(G)$ of a minimum set of edges that intersects every triangle of a graph $G$ is at most twice the size $ u(G)$ of a maximum set of edge-disjoint triangles of $G$. In this paper we present three results regarding Tuzas Conjecture. We verify it for graphs with treewidth at most $6$; we show that $tau(G)leq frac{3}{2}, u(G)$ for every planar triangulation $G$ different from $K_4$; and that $tau(G)leqfrac{9}{5}, u(G) + frac{1}{5}$ if $G$ is a maximal graph with treewidth 3. Our first result strengthens a result of Tuza, implying that $tau(G) leq 2, u(G)$ for every $K_8$-free chordal graph $G$.
We prove a conjecture of Ohba which says that every graph $G$ on at most $2chi(G)+1$ vertices satisfies $chi_ell(G)=chi(G)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
