Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA density bound for triangle-free $4$-critical graphs
218
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show every triangle-free $4$-critical graph $G$ satisfies $e(G) geq frac{5v(G)+2}{3}$.
rate research
Read More
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 class $mathcal{C}$ of graphs and a fixed graph $H$, the online Ramsey game for $H$ on $mathcal C$ is a game between two players Builder and Painter as follows: an unbounded set of vertices is given as an initial state, and on each turn Builder introduces a new edge with the constraint that the resulting graph must be in $mathcal C$, and Painter colors the new edge either red or blue. Builder wins the game if Painter is forced to make a monochromatic copy of $H$ at some point in the game. Otherwise, Painter can avoid creating a monochromatic copy of $H$ forever, and we say Painter wins the game. We initiate the study of characterizing the graphs $F$ such that for a given graph $H$, Painter wins the online Ramsey game for $H$ on $F$-free graphs. We characterize all graphs $F$ such that Painter wins the online Ramsey game for $C_3$ on the class of $F$-free graphs, except when $F$ is one particular graph. We also show that Painter wins the online Ramsey game for $C_3$ on the class of $K_4$-minor-free graphs, extending a result by Grytczuk, Ha{l}uszczak, and Kierstead.
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.
The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced triangle-free graphs with a given rank and characterize all such graphs achieving the maximum order.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
