Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLarge Monochromatic Components of Small Diameter
91
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Gyarfas conjectured in 2011 that every $r$-edge-colored $K_n$ contains a monochromatic component of bounded (perhaps three) diameter on at least $n/(r-1)$ vertices. Letzter proved this conjecture with diameter four. In this note we improve the result in the case of $r=3$: We show that in every $3$-edge-coloring of $K_n$ either there is a monochromatic component of diameter at most three on at least $n/2$ vertices or every color class is spanning and has diameter at most four.
rate research
Read More
We consider the question of the largest possible combinatorial diameter among $(d-1)$-dimensional simplicial complexes on $n$ vertices, denoted $H_s(n, d)$. Using a probabilistic construction we give a new lower bound on $H_s(n, d)$ that is within an $O(d^2)$ factor of the upper bound. This improves on the previously best-known lower bound which was within a factor of $e^{Theta(d)}$ of the upper bound. We also make a similar improvement in the case of pseudomanifolds.
In this work, we continue the study of vertex colorings of graphs, in which adjacent vertices are allowed to be of the same color as long as each monochromatic connected component is of relatively small cardinality. We focus on colorings with two and three available colors and present improved bounds on the size of the monochromatic connected components for two meaningful subclasses of planar graphs, namely maximal outerplanar graphs and complete planar 3-trees.
For $kgeq 1$, a $k$-colouring $c$ of $G$ is a mapping from $V(G)$ to ${1,2,ldots,k}$ such that $c(u) eq c(v)$ for any two non-adjacent vertices $u$ and $v$. The $k$-Colouring problem is to decide if a graph $G$ has a $k$-colouring. For a family of graphs ${cal H}$, a graph $G$ is ${cal H}$-free if $G$ does not contain any graph from ${cal H}$ as an induced subgraph. Let $C_s$ be the $s$-vertex cycle. In previous work (MFCS 2019) we examined the effect of bounding the diameter on the complexity of $3$-Colouring for $(C_3,ldots,C_s)$-free graphs and $H$-free graphs where $H$ is some polyad. Here, we prove for certain small values of $s$ that $3$-Colouring is polynomial-time solvable for $C_s$-free graphs of diameter $2$ and $(C_4,C_s)$-free graphs of diameter $2$. In fact, our results hold for the more general problem List $3$-Colouring. We complement these results with some hardness result for diameter $4$.
Let $Gamma$ denote a $Q$-polynomial distance-regular graph with vertex set $X$ and diameter $D$. Let $A$ denote the adjacency matrix of $Gamma$. Fix a base vertex $xin X$ and for $0 leq i leq D$ let $E^*_i=E^*_i(x)$ denote the projection matrix to the $i$th subconstituent space of $Gamma$ with respect to $x$. The Terwilliger algebra $T(x)$ of $Gamma$ with respect to $x$ is the semisimple subalgebra of $mathrm{Mat}_X(mathbb{C})$ generated by $A, E^*_0, E^*_1, ldots, E^*_D$. Remark that the isomorphism class of $T(x)$ depends on the choice of the base vertex $x$. We say $Gamma$ is pseudo-vertex-transitive whenever for any vertices $x,y in X$, the Terwilliger algebras $T(x)$ and $T(y)$ are isomorphic. In this paper we discuss pseudo-vertex transitivity for distance-regular graphs with diameter $Din {2,3,4}$. In the case of diameter $2$, a strongly regular graph $Gamma$ is thin, and $Gamma$ is pseudo-vertex-transitive if and only if every local graph of $Gamma$ has the same spectrum. In the case of diameter $3$, Taylor graphs are thin and pseudo-vertex-transitive. In the case of diameter $4$, antipodal tight graphs are thin and pseudo-vertex-transitive.
In this paper we study random induced subgraphs of the binary $n$-cube, $Q_2^n$. This random graph is obtained by selecting each $Q_2^n$-vertex with independent probability $lambda_n$. Using a novel construction of subcomponents we study the largest component for $lambda_n=frac{1+chi_n}{n}$, where $epsilonge chi_nge n^{-{1/3}+ delta}$, $delta>0$. We prove that there exists a.s. a unique largest component $C_n^{(1)}$. We furthermore show that $chi_n=epsilon$, $| C_n^{(1)}|sim alpha(epsilon) frac{1+chi_n}{n} 2^n$ and for $o(1)=chi_nge n^{-{1/3}+delta}$, $| C_n^{(1)}| sim 2 chi_n frac{1+chi_n}{n} 2^n$ holds. This improves the result of cite{Bollobas:91} where constant $chi_n=chi$ is considered. In particular, in case of $lambda_n=frac{1+epsilon} {n}$, our analysis implies that a.s. a unique giant component exists.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
