Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGraded Sparse Graphs and Matroids
440
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Sparse graphs and their associated matroids play an important role in rigidity theory, where they capture the combinatorics of generically rigid structures. We define a new family called {bf graded sparse graphs}, arising from generically pinned (completely immobilized) bar-and-joint frameworks and prove that they also form matroids. We address five problems on graded sparse graphs: {bf Decision}, {bf Extraction}, {bf Components}, {bf Optimization}, and {bf Extension}. We extend our {bf pebble game algorithms} to solve them.
rate research
Read More
Let $G$ be a simple $n$-vertex graph and $c$ be a colouring of $E(G)$ with $n$ colours, where each colour class has size at least $2$. We prove that $(G,c)$ contains a rainbow cycle of length at most $lceil frac{n}{2} rceil$, which is best possible. Our result settles a special case of a strengthening of the Caccetta-Haggkvist conjecture, due to Aharoni. We also show that the matroid generalization of our main result also holds for cographic matroids, but fails for binary matroids.
Pairs of graded graphs, together with the Fomin property of graded graph duality, are rich combinatorial structures providing among other a framework for enumeration. The prototypical example is the one of the Young graded graph of integer partitions, allowing us to connect number of standard Young tableaux and numbers of permutations. Here, we use operads, that algebraic devices abstracting the notion of composition of combinatorial objects, to build pairs of graded graphs. For this, we first construct a pair of graded graphs where vertices are syntax trees, the elements of free nonsymmetric operads. This pair of graphs is dual for a new notion of duality called $phi$-diagonal duality, similar to the ones introduced by Fomin. We also provide a general way to build pairs of graded graphs from operads, wherein underlying posets are analogous to the Young lattice. Some examples of operads leading to new pairs of graded graphs involving integer compositions, Motzkin paths, and $m$-trees are considered.
An (improper) graph colouring has defect $d$ if each monochromatic subgraph has maximum degree at most $d$, and has clustering $c$ if each monochromatic component has at most $c$ vertices. This paper studies defective and clustered list-colourings for graphs with given maximum average degree. We prove that every graph with maximum average degree less than $frac{2d+2}{d+2} k$ is $k$-choosable with defect $d$. This improves upon a similar result by Havet and Sereni [J. Graph Theory, 2006]. For clustered choosability of graphs with maximum average degree $m$, no $(1-epsilon)m$ bound on the number of colours was previously known. The above result with $d=1$ solves this problem. It implies that every graph with maximum average degree $m$ is $lfloor{frac{3}{4}m+1}rfloor$-choosable with clustering 2. This extends a result of Kopreski and Yu [Discrete Math., 2017] to the setting of choosability. We then prove two results about clustered choosability that explore the trade-off between the number of colours and the clustering. In particular, we prove that every graph with maximum average degree $m$ is $lfloor{frac{7}{10}m+1}rfloor$-choosable with clustering $9$, and is $lfloor{frac{2}{3}m+1}rfloor$-choosable with clustering $O(m)$. As an example, the later result implies that every biplanar graph is 8-choosable with bounded clustering. This is the best known result for the clustered version of the earth-moon problem. The results extend to the setting where we only consider the maximum average degree of subgraphs with at least some number of vertices. Several applications are presented.
By considering graphs as discrete analogues of Riemann surfaces, Baker and Norine (Adv. Math. 2007) developed a concept of linear systems of divisors for graphs. Building on this idea, a concept of gonality for graphs has been defined and has generated much recent interest. We show that there are connected graphs of treewidth 2 of arbitrarily high gonality. We also show that there exist pairs of connected graphs ${G,H}$ such that $Hsubseteq G$ and $H$ has strictly lower gonality than $G$. These results resolve three open problems posed in a recent survey by Norine (Surveys in Combinatorics 2015).
We apply the Discharging Method to prove the 1,2,3-Conjecture and the 1,2-Conjecture for graphs with maximum average degree less than 8/3. Stronger results on these conjectures have been proved, but this is the first application of discharging to them, and the structure theorems and reducibility results are of independent interest.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
