Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn semi-transitive orientability of triangle-free graphs
76
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We consider the class of semi-transitively orientable graphs, which is a much larger class of graphs compared to transitively orientable graphs, in other words, comparability graphs. Ever since the concept of a semi-transitive orientation was defined as a crucial ingredient of the characterization of alternation graphs, also knownas word-representable graphs, it has sparked independent interest. In this paper, we investigate graph operations and graph products that preserve semitransitive orientability of graphs. The main theme of this paper is to determine which graph operations satisfy the following statement: if a graph operation is possible on a semitransitively orientable graph, then the same graph operation can be executed on the graph while preserving the semi-transitive orientability. We were able to prove that this statement is true for edge-deletions, edge-additions, and edge-liftings. Moreover, for all three graph operations,we showthat the initial semi-transitive orientation can be extended to the new graph obtained by the graph operation. Also, Kitaev and Lozin explicitly asked if certain graph products preserve the semitransitive orientability. We answer their question in the negative for the tensor product, lexicographic product, and strong product.We also push the investigation further and initiate the study of sufficient conditions that guarantee a certain graph operation to preserve the semi-transitive orientability.
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 edge between $v_0$ and $v_k$, or $v_irightarrow v_j$ is an edge for all $0leq i<jleq k$. An undirected graph is semi-transitive if it admits a semi-transitive orientation. Semi-transitive graphs include several important classes of graphs such as 3-colorable graphs, comparability graphs, and circle graphs, and they are precisely the class of word-representable graphs studied extensively in the literature. In this paper, we study semi-transitive orientability of the celebrated Kneser graph $K(n,k)$, which is the graph whose vertices correspond to the $k$-element subsets of a set of $n$ elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. We show that for $ngeq 15k-24$, $K(n,k)$ is not semi-transitive, while for $kleq nleq 2k+1$, $K(n,k)$ is semi-transitive. Also, we show computationally that a subgraph $S$ on 16 vertices and 36 edges of $K(8,3)$, and thus $K(8,3)$ itself on 56 vertices and 280 edges, is non-semi-transitive. $S$ and $K(8,3)$ are the first explicit examples of triangle-free non-semi-transitive graphs, whose existence was established via ErdH{o}s theorem by Halld{o}rsson et al. in 2011. Moreover, we show that the complement graph $overline{K(n,k)}$ of $K(n,k)$ is semi-transitive if and only if $ngeq 2k$.
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$.
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$.
We prove an asymptotically tight lower bound on the average size of independent sets in a triangle-free graph on $n$ vertices with maximum degree $d$, showing that an independent set drawn uniformly at random from such a graph has expected size at least $(1+o_d(1)) frac{log d}{d}n$. This gives an alternative proof of Shearers upper bound on the Ramsey number $R(3,k)$. We then prove that the total number of independent sets in a triangle-free graph with maximum degree $d$ is at least $exp left[left(frac{1}{2}+o_d(1) right) frac{log^2 d}{d}n right]$. The constant $1/2$ in the exponent is best possible. In both cases, tightness is exhibited by a random $d$-regular graph. Both results come from considering the hard-core model from statistical physics: a random independent set $I$ drawn from a graph with probability proportional to $lambda^{|I|}$, for a fugacity parameter $lambda>0$. We prove a general lower bound on the occupancy fraction (normalized expected size of the random independent set) of the hard-core model on triangle-free graphs of maximum degree $d$. The bound is asymptotically tight in $d$ for all $lambda =O_d(1)$. We conclude by stating several conjectures on the relationship between the average and maximum size of an independent set in a triangle-free graph and give some consequences of these conjectures in Ramsey theory.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
