Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPolynomial $chi$-binding functions for $t$-broom-free graphs
135
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For any positive integer $t$, a emph{$t$-broom} is a graph obtained from $K_{1,t+1}$ by subdividing an edge once. In this paper, we show that, for graphs $G$ without induced $t$-brooms, we have $chi(G) = o(omega(G)^{t+1})$, where $chi(G)$ and $omega(G)$ are the chromatic number and clique number of $G$, respectively. When $t=2$, this answers a question of Schiermeyer and Randerath. Moreover, for $t=2$, we strengthen the bound on $chi(G)$ to $7.5omega(G)^2$, confirming a conjecture of Sivaraman. For $tgeq 3$ and {$t$-broom, $K_{t,t}$}-free graphs, we improve the bound to $o(omega^{t-1+frac{2}{t+1}})$.
rate research
Read More
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.
Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ or $H_2$. Let $P_t$ be the path on $t$ vertices and $K_t$ be the complete graph on $t$ vertices. The diamond is the graph obtained from $K_4$ by removing an edge. In this paper we show that every ($P_6$, diamond)-free graph $G$ satisfies $chi(G)le omega(G)+3$, where $chi(G)$ and $omega(G)$ are the chromatic number and clique number of $G$, respectively. Our bound is attained by the complement of the famous 27-vertex Schlafli graph. Our result unifies previously known results on the existence of linear $chi$-binding functions for several graph classes. Our proof is based on a reduction via the Strong Perfect Graph Theorem to imperfect ($P_6$, diamond)-free graphs, a careful analysis of the structure of those graphs, and a computer search that relies on a well-known characterization of 3-colourable $(P_6,K_3)$-free graphs.
By using the Szemeredi Regularity Lemma, Alon and Sudakov recently extended the classical Andrasfai-Erd~os-Sos theorem to cover general graphs. We prove, without using the Regularity Lemma, that the following stronger statement is true. Given any (r-1)-partite graph H whose smallest part has t vertices, and any fixed c>0, there exists a constant C such that whenever G is an n-vertex graph with minimum degree at least ((3r-4)/(3r-1)+c)n, either G contains H, or we can delete at most Cn^(2-1/t) edges from G to yield an r-partite graph.
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.
We consider the Ihara zeta function $zeta(u,X//G)$ and Artin-Ihara $L$-function of the quotient graph of groups $X//G$, where $G$ is a group acting on a finite graph $X$ with trivial edge stabilizers. We determine the relationship between the primes of $X$ and $X//G$ and show that $Xto X//G$ can be naturally viewed as an unramified Galois covering of graphs of groups. We show that the $L$-function of $X//G$ evaluated at the regular representation is equal to $zeta(u,X)$ and that $zeta(u,X//G)$ divides $zeta(u,X)$. We derive two-term and three-term determinant formulas for the zeta and $L$-functions, and compute several examples of $L$-functions of edge-free quotients of the tetrahedron graph $K_4$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
