Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPentagons in triangle-free graphs
81
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For all $nge 9$, we show that the only triangle-free graphs on $n$ vertices maximizing the number $5$-cycles are balanced blow-ups of a 5-cycle. This completely resolves a conjecture by ErdH{o}s, and extends results by Grzesik and Hatami, Hladky, Kr{a}l, Norin and Razborov, where they independently showed this same result for large $n$ and for all $n$ divisible by $5$.
rate research
Read More
Given a graph $G=(V,E)$ whose vertices have been properly coloured, we say that a path in $G$ is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai-Roy-Vitaver Theorem that every properly coloured graph contains a colourful path on $chi(G)$ vertices. We explore a conjecture that states that every properly coloured triangle-free graph $G$ contains an induced colourful path on $chi(G)$ vertices and prove its correctness when the girth of $G$ is at least $chi(G)$. Recent work on this conjecture by Gyarfas and Sarkozy, and Scott and Seymour has shown the existence of a function $f$ such that if $chi(G)geq f(k)$, then an induced colourful path on $k$ vertices is guaranteed to exist in any properly coloured triangle-free graph $G$.
Any two reduced expressions for the same Coxeter group element are related by a sequence of commutation and braid moves. We say that two reduced expressions are braid equivalent if they are related via a sequence of braid moves, and the corresponding equivalence classes are called braid classes. Each braid class can be encoded in terms of a braid graph in a natural way. In this paper, we study the structure of braid graphs in simply-laced Coxeter systems. We prove that every reduced expression has a unique factorization as a product of so-called links, which in turn induces a decomposition of the braid graph into a box product of the braid graphs for each link factor. When the Coxeter graph has no three-cycles, we use the decomposition to prove that braid graphs are cubical by constructing an embedding of the braid graph into a hypercube graph whose image is an induced subgraph of the hypercube. For a special class of links, called Fibonacci links, we prove that this embedding is an isometry from the corresponding braid graph to a Fibonacci cube graph.
An orientation of a graph is semi-transitive if it is acyclic, and for any directed path $v_0rightarrow v_1rightarrow cdotsrightarrow v_k$ either there is no arc between $v_0$ and $v_k$, or $v_irightarrow v_j$ is an arc for all $0leq i<jleq k$. An undirected graph is semi-transitive if it admits a semi-transitive orientation. Semi-transitive graphs generalize several important classes of graphs and they are precisely the class of word-representable graphs studied extensively in the literature. Determining if a triangle-free graph is semi-transitive is an NP-hard problem. The existence of non-semi-transitive triangle-free graphs was established via ErdH{o}s theorem by Halld{o}rsson and the authors in 2011. However, no explicit examples of such graphs were known until recent work of the first author and Saito who have shown computationally that a certain subgraph on 16 vertices of the triangle-free Kneser graph $K(8,3)$ is not semi-transitive, and have raised the question on the existence of smaller triangle-free non-semi-transitive graphs. In this paper we prove that the smallest triangle-free 4-chromatic graph on 11 vertices (the Grotzsch graph) and the smallest triangle-free 4-chromatic 4-regular graph on 12 vertices (the Chvatal graph) are not semi-transitive. Hence, the Grotzsch graph is the smallest triangle-free non-semi-transitive graph. We also prove the existence of semi-transitive graphs of girth 4 with chromatic number 4 including a small one (the circulant graph $C(13;1,5)$ on 13 vertices) and dense ones (Tofts graphs). Finally, we show that each $4$-regular circulant graph (possibly containing triangles) is semi-transitive.
In 1967, ErdH{o}s asked for the greatest chromatic number, $f(n)$, amongst all $n$-vertex, triangle-free graphs. An observation of ErdH{o}s and Hajnal together with Shearers classical upper bound for the off-diagonal Ramsey number $R(3, t)$ shows that $f(n)$ is at most $(2 sqrt{2} + o(1)) sqrt{n/log n}$. We improve this bound by a factor $sqrt{2}$, as well as obtaining an analogous bound on the list chromatic number which is tight up to a constant factor. A bound in terms of the number of edges that is similarly tight follows, and these results confirm a conjecture of Cames van Batenburg, de Joannis de Verclos, Kang, and Pirot.
An orientation of $G$ is a digraph obtained from $G$ by replacing each edge by exactly one of two possible arcs with the same endpoints. We call an orientation emph{proper} if neighbouring vertices have different in-degrees. The proper orientation number of a graph $G$, denoted by $vec{chi}(G)$, is the minimum maximum in-degree of a proper orientation of G. Araujo et al. (Theor. Comput. Sci. 639 (2016) 14--25) asked whether there is a constant $c$ such that $vec{chi}(G)leq c$ for every outerplanar graph $G$ and showed that $vec{chi}(G)leq 7$ for every cactus $G.$ We prove that $vec{chi}(G)leq 3$ if $G$ is a triangle-free $2$-connected outerplanar graph and $vec{chi}(G)leq 4$ if $G$ is a triangle-free bridgeless outerplanar graph.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
