Results 41 to 50 of about 6,485 (204)
On the Rainbow Vertex-Connection
Discussiones Mathematicae Graph Theory, 2013 A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that ...
Li Xueliang, Shi Yongtang
doaj +1 more source
On the Hardness of Switching to a Small Number of Edges
Journal of Graph Theory, EarlyView.ABSTRACT Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non‐adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching‐equivalent if one can be made isomorphic to the other one by a sequence of switches. Jelínková et al. [DMTCS 13, no. 2, 2011]
Vít Jelínek +2 more
wiley +1 more source
Compatible cycles and CHY integrals
Journal of High Energy Physics, 2019 The CHY construction naturally associates a vector in ℝ(n−3)! to every 2- regular graph with n vertices. Partial amplitudes in the biadjoint scalar theory are given by the inner product of vectors associated with a pair of cycles.
Freddy Cachazo +2 more
doaj +1 more source
Linear Versus Centred Colouring via Pseudogrids
Journal of Graph Theory, EarlyView.ABSTRACT A centred colouring of a graph is a vertex colouring in which every connected subgraph contains a vertex whose colour is unique and a linear colouring is a vertex colouring in which every (not‐necessarily induced) path contains a vertex whose colour is unique. For a graph G $G$, the centred chromatic number χ cen ( G ) ${\chi }_{\text{cen}}(G)$
Prosenjit Bose +4 more
wiley +1 more source
Coxeter-biCatalan combinatorics [PDF]
Discrete Mathematics & Theoretical Computer Science, 2015 We consider several counting problems related to Coxeter-Catalan combinatorics and conjecture that the problems all have the same answer, which we call the $W$ -biCatalan number. We prove the conjecture in many cases.
Emily Barnard, Nathan Reading
doaj +1 more source
Journal of Graph Theory, EarlyView.ABSTRACT In an effort to understand the complexity of the maximum independent set problem, Chvátal introduced t‐perfect graphs. While a full characterization of this class remains open, important progress has been made for claw‐free graphs [Bruhn and Stein, Math. Program. 2012] and P 5 ${P}_{5}$‐free graphs [Bruhn and Fuchs, SIAM J. Discrete Math. 2017]
Yixin Cao, Shenghua Wang
wiley +1 more source
Combinatorics of Explicit Substitutions [PDF]
Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming, 2018 $λ\upsilon$ is an extension of the $λ$-calculus which internalises the calculus of substitutions. In the current paper, we investigate the combinatorial properties of $λ\upsilon$ focusing on the quantitative aspects of substitution resolution. We exhibit an unexpected correspondence between the counting sequence for $λ\upsilon$-terms and famous Catalan
Bendkowski, Maciej, Lescanne, Pierre
openaire +3 more sources
Tree Independence Number III. Thetas, Prisms and Stars
Journal of Graph Theory, EarlyView.ABSTRACT We prove that for every t ∈ N $t\in {\mathbb{N}}$ there exists τ = τ ( t ) ∈ N $\tau =\tau (t)\in {\mathbb{N}}$ such that every (theta, prism, K 1 , t ${K}_{1,t}$)‐free graph has tree independence number at most τ $\tau $ (where we allow “prisms” to have one path of length zero).
Maria Chudnovsky +2 more
wiley +1 more source
Combinatorics of Positroids [PDF]
Discrete Mathematics & Theoretical Computer Science, 2009 Recently Postnikov gave a combinatorial description of the cells in a totally-nonnegative Grassmannian. These cells correspond to a special class of matroids called positroids.
Suho Oh
doaj +1 more source
Saturated Partial Embeddings of Planar Graphs
Journal of Graph Theory, EarlyView.ABSTRACT In this work, we study how far one can deviate from optimal behavior when embedding a planar graph. For a planar graph G $G$, we say that a plane subgraph H ⊆ G $H\subseteq G$ is a plane‐saturated subgraph if adding any edge (possibly with new vertices) to H $H$ would either violate planarity or make the resulting graph no longer a subgraph of
Alexander Clifton, Nika Salia
wiley +1 more source