Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTriangles in $C_5$-free graphs and Hypergraphs of Girth Six
82
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We introduce a new approach and prove that the maximum number of triangles in a $C_5$-free graph on $n$ vertices is at most $$(1 + o(1)) frac{1}{3 sqrt 2} n^{3/2}.$$ We also show a connection to $r$-uniform hypergraphs without (Berge) cycles of length less than six, and estimate their maximum possible size.
rate research
Read More
Let $S subset mathbb{R}^2$ be a set of $n$ sites, where each $s in S$ has an associated radius $r_s > 0$. The disk graph $D(S)$ is the undirected graph with vertex set $S$ and an undirected edge between two sites $s, t in S$ if and only if $|st| leq r_s + r_t$, i.e., if the disks with centers $s$ and $t$ and respective radii $r_s$ and $r_t$ intersect. Disk graphs are used to model sensor networks. Similarly, the transmission graph $T(S)$ is the directed graph with vertex set $S$ and a directed edge from a site $s$ to a site $t$ if and only if $|st| leq r_s$, i.e., if $t$ lies in the disk with center $s$ and radius $r_s$. We provide algorithms for detecting (directed) triangles and, more generally, computing the length of a shortest cycle (the girth) in $D(S)$ and in $T(S)$. These problems are notoriously hard in general, but better solutions exist for special graph classes such as planar graphs. We obtain similarly efficient results for disk graphs and for transmission graphs. More precisely, we show that a shortest (Euclidean) triangle in $D(S)$ and in $T(S)$ can be found in $O(n log n)$ expected time, and that the (weighted) girth of $D(S)$ can be found in $O(n log n)$ expected time. For this, we develop new tools for batched range searching that may be of independent interest.
As usual, $P_n$ ($n geq 1$) denotes the path on $n$ vertices, and $C_n$ ($n geq 3$) denotes the cycle on $n$ vertices. For a family $mathcal{H}$ of graphs, we say that a graph $G$ is $mathcal{H}$-free if no induced subgraph of $G$ is isomorphic to any graph in $mathcal{H}$. We present a decomposition theorem for the class of $(P_7,C_4,C_5)$-free graphs; in fact, we give a complete structural characterization of $(P_7,C_4,C_5)$-free graphs that do not admit a clique-cutset. We use this decomposition theorem to show that the class of $(P_7,C_4,C_5)$-free graphs is $chi$-bounded by a linear function (more precisely, every $(P_7,C_4,C_5)$-free graph $G$ satisfies $chi(G) leq frac{3}{2} omega(G)$). We also use the decomposition theorem to construct an $O(n^3)$ algorithm for the minimum coloring problem, an $O(n^2m)$ algorithm for the maximum weight stable set problem, and an $O(n^3)$ algorithm for the maximum weight clique problem for this class, where $n$ denotes the number of vertices and $m$ the number of edges of the input graph.
Bollobas and Nikiforov [J. Combin. Theory, Ser. B. 97 (2007) 859--865] conjectured the following. If $G$ is a $K_{r+1}$-free graph on at least $r+1$ vertices and $m$ edges, then $lambda^2_1(G)+lambda^2_2(G)leq frac{r-1}{r}cdot2m$, where $lambda_1(G)$ and $lambda_2(G)$ are the largest and the second largest eigenvalues of the adjacency matrix $A(G)$, respectively. In this paper, we confirm the conjecture in the case $r=2$, by using tools from doubly stochastic matrix theory, and also characterize all families of extremal graphs. Motivated by classic theorems due to ErdH{o}s and Nosal respectively, we prove that every non-bipartite graph $G$ of order $n$ and size $m$ contains a triangle, if one of the following is true: (1) $lambda_1(G)geqsqrt{m-1}$ and $G eq C_5cup (n-5)K_1$; and (2) $lambda_1(G)geq lambda_1(S(K_{lfloorfrac{n-1}{2}rfloor,lceilfrac{n-1}{2}rceil}))$ and $G eq S(K_{lfloorfrac{n-1}{2}rfloor,lceilfrac{n-1}{2}rceil})$, where $S(K_{lfloorfrac{n-1}{2}rfloor,lceilfrac{n-1}{2}rceil})$ is obtained from $K_{lfloorfrac{n-1}{2}rfloor,lceilfrac{n-1}{2}rceil}$ by subdividing an edge. Both conditions are best possible. We conclude this paper with some open problems.
Assume $ k $ is a positive integer, $ lambda={k_1,k_2,...,k_q} $ is a partition of $ k $ and $ G $ is a graph. A $lambda$-assignment of $ G $ is a $ k $-assignment $ L $ of $ G $ such that the colour set $ bigcup_{vin V(G)} L(v) $ can be partitioned into $ q $ subsets $ C_1cup C_2cupcdotscup C_q $ and for each vertex $ v $ of $ G $, $ |L(v)cap C_i|=k_i $. We say $ G $ is $lambda$-choosable if for each $lambda$-assignment $ L $ of $ G $, $ G $ is $ L $-colourable. In particular, if $ lambda={k} $, then $lambda$-choosable is the same as $ k $-choosable, if $ lambda={1, 1,...,1} $, then $lambda$-choosable is equivalent to $ k $-colourable. For the other partitions of $ k $ sandwiched between $ {k} $ and $ {1, 1,...,1} $ in terms of refinements, $lambda$-choosability reveals a complex hierarchy of colourability of graphs. Assume $lambda={k_1, ldots, k_q} $ is a partition of $ k $ and $lambda $ is a partition of $ kge k $. We write $ lambdale lambda $ if there is a partition $lambda={k_1, ldots, k_q}$ of $k$ with $k_i ge k_i$ for $i=1,2,ldots, q$ and $lambda$ is a refinement of $lambda$. It follows from the definition that if $ lambdale lambda $, then every $lambda$-choosable graph is $lambda$-choosable. It was proved in [X. Zhu, A refinement of choosability of graphs, J. Combin. Theory, Ser. B 141 (2020) 143 - 164] that the converse is also true. This paper strengthens this result and proves that for any $ lambda otle lambda $, for any integer $g$, there exists a graph of girth at least $g$ which is $lambda$-choosable but not $lambda$-choosable.
Let $G$ be a ${C_4, C_5}$-free planar graph with a list assignment $L$. Suppose a preferred color is given for some of the vertices. We prove that if all lists have size at least four, then there exists an $L$-coloring respecting at least a constant fraction of the preferences.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
