Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userChi-boundedness of graph classes excluding wheel vertex-minors
85
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A class of graphs is $chi$-bounded if there exists a function $f:mathbb Nrightarrow mathbb N$ such that for every graph $G$ in the class and an induced subgraph $H$ of $G$, if $H$ has no clique of size $q+1$, then the chromatic number of $H$ is less than or equal to $f(q)$. We denote by $W_n$ the wheel graph on $n+1$ vertices. We show that the class of graphs having no vertex-minor isomorphic to $W_n$ is $chi$-bounded. This generalizes several previous results; $chi$-boundedness for circle graphs, for graphs having no $W_5$ vertex-minors, and for graphs having no fan vertex-minors.
rate research
Read More
We show that for pairs $(Q,R)$ and $(S,T)$ of disjoint subsets of vertices of a graph $G$, if $G$ is sufficiently large, then there exists a vertex $v$ in $V(G)-(Qcup Rcup Scup T)$ such that there are two ways to reduce $G$ by a vertex-minor operation while preserving the connectivity between $Q$ and $R$ and the connectivity between $S$ and $T$. Our theorem implies an analogous theorem of Chen and Whittle (2014) for matroids restricted to binary matroids.
A cornerstone theorem in the Graph Minors series of Robertson and Seymour is the result that every graph $G$ with no minor isomorphic to a fixed graph $H$ has a certain structure. The structure can then be exploited to deduce far-reaching consequences. The exact statement requires some explanation, but roughly it says that there exist integers $k,n$ depending on $H$ only such that $0<k<n$ and for every $ntimes n$ grid minor $J$ of $G$ the graph $G$ has a a $k$-near embedding in a surface $Sigma$ that does not embed $H$ in such a way that a substantial part of $J$ is embedded in $Sigma$. Here a $k$-near embedding means that after deleting at most $k$ vertices the graph can be drawn in $Sigma$ without crossings, except for local areas of non-planarity, where crossings are permitted, but at most $k$ of these areas are attached to the rest of the graph by four or more vertices and inside those the graph is constrained in a different way, again depending on the parameter $k$. The original and only proof so far is quite long and uses many results developed in the Graph Minors series. We give a proof that uses only our earlier paper [A new proof of the flat wall theorem, {it J.~Combin. Theory Ser. B bf 129} (2018), 158--203] and results from graduate textbooks. Our proof is constructive and yields a polynomial time algorithm to construct such a structure. We also give explicit constants for the structure theorem, whereas the original proof only guarantees the existence of such constants.
Frame matroids and lifted-graphic matroids are two distinct minor-closed classes of matroids, each of which generalises the class of graphic matroids. The class of quasi-graphic matroids, recently introduced by Geelen, Gerards, and Whittle, simultaneously generalises both the classes of frame and lifted-graphic matroids. Let $mathcal{M}$ be one of these three classes, and let $r$ be a positive integer. We show that $mathcal{M}$ has only a finite number of excluded minors of rank $r$.
In 2009, Brown gave a set of conditions which when satisfied imply that a Feynman integral evaluates to a multiple zeta value. One of these conditions is called reducibility, which loosely says there is an order of integration for the Feynman integral for which Browns techniques will succeed. Reducibility can be abstracted away from the Feynman integral to just being a condition on two polynomials, the first and second Symanzik polynomials. These polynomials can be defined from graphs, and thus reducibility is a property of graphs. We prove that for a fixed number of external momenta and no masses, reducibility is graph minor closed, correcting the previously claimed proofs of this fact. A computational study of reducibility was undertaken by Bogner and L{u}ders who found that for graphs with $4$-on-shell momenta and no masses, $K_{4}$ with momenta on each vertex is a forbidden minor. We add to this and find that when we restrict to graphs with four on-shell external momenta the following graphs are forbidden minors: $K_{4}$ with momenta on each vertex, $W_{4}$ with external momenta on the rim vertices, $K_{2,4}$ with external momenta on the large side of the bipartition, and one other graph. We do not expect that these minors characterize reducibility, so instead we give structural characterizations of the graphs not containing subsets of these minors. We characterize graphs not containing a rooted $K_{4}$ or rooted $W_{4}$ minor, graphs not containing rooted $K_{4}$ or rooted $W_{4}$ or rooted $K_{2,4}$ minors, and also a characterization of graphs not containing all of the known forbidden minors. Some comments are made on graphs not containing $K_{3,4}$, $K_{6}$ or a graph related to Wagners graph as a minor.
We prove that any $n$-node graph $G$ with diameter $D$ admits shortcuts with congestion $O(delta D log n)$ and dilation $O(delta D)$, where $delta$ is the maximum edge-density of any minor of $G$. Our proof is simple, elementary, and constructive - featuring a $tilde{Theta}(delta D)$-round distributed construction algorithm. Our results are tight up to $tilde{O}(1)$ factors and generalize, simplify, unify, and strengthen several prior results. For example, for graphs excluding a fixed minor, i.e., graphs with constant $delta$, only a $tilde{O}(D^2)$ bound was known based on a very technical proof that relies on the Robertson-Seymour Graph Structure Theorem. A direct consequence of our result is that many graph families, including any minor-excluded ones, have near-optimal $tilde{Theta}(D)$-round distributed algorithms for many fundamental communication primitives and optimization problems including minimum spanning tree, minimum cut, and shortest-path approximations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
