Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn improvement to the vertex-splitting conjecture
127
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For a simple graph $G$, denote by $n$, $Delta(G)$, and $chi(G)$ its order, maximum degree, and chromatic index, respectively. A connected class 2 graph $G$ is edge-chromatic critical if $chi(G-e)<Delta(G)+1$ for every edge $e$ of $G$. Define $G$ to be overfull if $|E(G)|>Delta(G) lfloor n/2 rfloor$. Clearly, overfull graphs are class 2 and any graph obtained from a regular graph of even order by splitting a vertex is overfull. Let $G$ be an $n$-vertex connected regular class 1 graph with $Delta(G) >n/3$. Hilton and Zhao in 1997 conjectured that if $G^*$ is obtained from $G$ by splitting one vertex of $G$ into two vertices, then $G^*$ is edge-chromatic critical, and they verified the conjecture for graphs $G$ with $Delta(G)ge frac{n}{2}(sqrt{7}-1)approx 0.82n$. The graph $G^*$ is easily verified to be overfull, and so the hardness of the conjecture lies in showing that the deletion of every of its edge decreases the chromatic index. Except in 2002, Song showed that the conjecture is true for a special class of graphs $G$ with $Delta(G)ge frac{n}{2}$, no other progress on this conjecture had been made. In this paper, we confirm the conjecture for graphs $G$ with $Delta(G) ge 0.75n$.
rate research
Read More
We give a short proof of a result of Jordan and Tanigawa that a 4-connected graph which has a spanning planar triangulation as a proper subgraph is generically globally rigid in R^3. Our proof is based on a new sufficient condition for the so called vertex splitting operation to preserve generic global rigidity in R^d.
This report formulates a conjectural combinatorial rule that positively expands Grothendieck polynomials into Lascoux polynomials. It generalizes one such formula expanding Schubert polynomials into key polynomials, and refines another one expanding stable Grothendieck polynomials.
The graph reconstruction conjecture asserts that every finite simple graph on at least three vertices can be reconstructed up to isomorphism from its deck - the collection of its vertex-deleted subgraphs. Kocays Lemma is an important tool in graph reconstruction. Roughly speaking, given the deck of a graph $G$ and any finite sequence of graphs, it gives a linear constraint that every reconstruction of $G$ must satisfy. Let $psi(n)$ be the number of distinct (mutually non-isomorphic) graphs on $n$ vertices, and let $d(n)$ be the number of distinct decks that can be constructed from these graphs. Then the difference $psi(n) - d(n)$ measures how many graphs cannot be reconstructed from their decks. In particular, the graph reconstruction conjecture is true for $n$-vertex graphs if and only if $psi(n) = d(n)$. We give a framework based on Kocays lemma to study this discrepancy. We prove that if $M$ is a matrix of covering numbers of graphs by sequences of graphs, then $d(n) geq mathsf{rank}_mathbb{R}(M)$. In particular, all $n$-vertex graphs are reconstructible if one such matrix has rank $psi(n)$. To complement this result, we prove that it is possible to choose a family of sequences of graphs such that the corresponding matrix $M$ of covering numbers satisfies $d(n) = mathsf{rank}_mathbb{R}(M)$.
The Strong Nine Dragon Tree Conjecture asserts that for any integers $k$ and $d$ any graph with fractional arboricity at most $k + frac{d}{d+k+1}$ decomposes into $k+1$ forests, such that for at least one of the forests, every connected component contains at most $d$ edges. We prove this conjecture when $d leq k+1$. We also prove an approximate version of this conjecture, that is, we prove that for any positive integers $k$ and $d$, any graph with fractional arboricity at most $k + frac{d}{d+k+1}$ decomposes into $k+1$ forests, such that one for at least one of the forests, every connected component contains at most $d + frac{d(k (2lceil frac{d}{k+1} +2 rceil)^{lceil frac{d}{k+1} + 2) rceil} - k)}{k+1} $ edges.
Hedetniemi conjectured in 1966 that $chi(G times H) = min{chi(G), chi(H)}$ for all graphs $G$ and $H$. Here $Gtimes H$ is the graph with vertex set $ V(G)times V(H)$ defined by putting $(x,y)$ and $(x,y)$ adjacent if and only if $xxin E(G)$ and $yyin E(H)$. This conjecture received a lot of attention in the past half century. Recently, Shitov refuted this conjecture. Let $p$ be the minimum number of vertices in a graph of odd girth $7$ and fractional chromatic number greater than $3+4/(p-1)$. Shitovs proof shows that Hedetniemis conjecture fails for some graphs with chromatic number about $p^22^{p+1} $ and with about $(p^22^{p+1})^{p^32^{p-1}} $ vertices. In this paper, we show that the conjecture fails already for some graphs $G$ and $H$ with chromatic number $3lceil frac {p+1}2 rceil $ and with $p lceil (p-1)/2 rceil$ and $3 lceil frac {p+1}2 rceil (p+1)-p$ vertices, respectively. The currently known upper bound for $p$ is $148$. Thus Hedetniemis conjecture fails for some graphs $G$ and $H$ with chromatic number $225$, and with $10,952$ and $33,377$ vertices, respectively.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
