Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDensities of 3-vertex graphs
79
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let d_i(G) be the density of the 3-vertex i-edge graph in a graph G, i.e., the probability that three random vertices induce a subgraph with i edges. Let S be the set of all quadruples (d_0,d_1,d_2,d_3) that are arbitrary close to 3-vertex graph densities in arbitrary large graphs. Huang, Linial, Naves, Peled and Sudakov have recently determined the projection of the set S to the (d_0,d_3) plane. We determine the projection of the set S to all the remaining planes.
rate research
Read More
A path in a vertex-colored graph is called emph{conflict free} if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be emph{conflict-free vertex-connected} if any two vertices of the graph are connected by a conflict-free path. This paper investigates the question: For a connected graph $G$, what is the smallest number of colors needed in a vertex-coloring of $G$ in order to make $G$ conflict-free vertex-connected. As a result, we get that the answer is easy for $2$-connected graphs, and very difficult for connected graphs with more cut-vertices, including trees.
We initiate a systematic study of the fractional vertex-arboricity of planar graphs and demonstrate connections to open problems concerning both fractional coloring and the size of the largest induced forest in planar graphs. In particular, the following three long-standing conjectures concern the size of a largest induced forest in a planar graph, and we conjecture that each of these can be generalized to the setting of fractional vertex-arboricity. In 1979, Albertson and Berman conjectured that every planar graph has an induced forest on at least half of its vertices, in 1987, Akiyama and Watanabe conjectured that every bipartite planar graph has an induced forest on at least five-eighths of its vertices, and in 2010, Kowalik, Luv{z}ar, and v{S}krekovski conjectured that every planar graph of girth at least five has an induced forest on at least seven-tenths of its vertices. We make progress toward the fractional generalization of the latter of these, by proving that every planar graph of girth at least five has fractional vertex-arboricity at most $2 - 1/324$.
We generalise the standard constructions of a Cayley graph in terms of a group presentation by allowing some vertices to obey different relators than others. The resulting notion of presentation allows us to represent every vertex transitive graph. As an intermediate step, we prove that every countably infinite, connected, vertex transitive graph has a perfect matching. Incidentally, we construct an example of a 2-ended cubic vertex transitive graph which is not a Cayley graph, answering a question of Watkins from 1990.
A graph $G$ is $k$-$weighted-list-antimagic$ if for any vertex weighting $omegacolon V(G)tomathbb{R}$ and any list assignment $Lcolon E(G)to2^{mathbb{R}}$ with $|L(e)|geq |E(G)|+k$ there exists an edge labeling $f$ such that $f(e)in L(e)$ for all $ein E(G)$, labels of edges are pairwise distinct, and the sum of the labels on edges incident to a vertex plus the weight of that vertex is distinct from the sum at every other vertex. In this paper we prove that every graph on $n$ vertices having no $K_1$ or $K_2$ component is $lfloor{frac{4n}{3}}rfloor$-weighted-list-antimagic. An oriented graph $G$ is $k$-$oriented-antimagic$ if there exists an injective edge labeling from $E(G)$ into ${1,dotsc,|E(G)|+k}$ such that the sum of the labels on edges incident to and oriented toward a vertex minus the sum of the labels on edges incident to and oriented away from that vertex is distinct from the difference of sums at every other vertex. We prove that every graph on $n$ vertices with no $K_1$ component admits an orientation that is $lfloor{frac{2n}{3}}rfloor$-oriented-antimagic.
A (vertex) $ell$-ranking is a labelling $varphi:V(G)tomathbb{N}$ of the vertices of a graph $G$ with integer colours so that for any path $u_0,ldots,u_p$ of length at most $ell$, $varphi(u_0) eqvarphi(u_p)$ or $varphi(u_0)<max{varphi(u_0),ldots,varphi(u_p)}$. We show that, for any fixed integer $ellge 2$, every $n$-vertex planar graph has an $ell$-ranking using $O(log n/logloglog n)$ colours and this is tight even when $ell=2$; for infinitely many values of $n$, there are $n$-vertex planar graphs, for which any 2-ranking requires $Omega(log n/logloglog n)$ colours. This result also extends to bounded genus graphs. In developing this proof we obtain optimal bounds on the number of colours needed for $ell$-ranking graphs of treewidth $t$ and graphs of simple treewidth $t$. These upper bounds are constructive and give $O(nlog n)$-time algorithms. Additional results that come from our techniques include new sublogarithmic upper bounds on the number of colours needed for $ell$-rankings of apex minor-free graphs and $k$-planar graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
