Results 11 to 20 of about 1,747,033 (270)
Computing Minimum Rainbow and Strong Rainbow Colorings of Block Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 A path in an edge-colored graph $G$ is rainbow if no two edges of it are colored the same. The graph $G$ is rainbow-connected if there is a rainbow path between every pair of vertices.
Melissa Keranen, Juho Lauri
doaj +1 more source
Gallai's Path Decomposition for 2-degenerate Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 Gallai's path decomposition conjecture states that if $G$ is a connected graph on $n$ vertices, then the edges of $G$ can be decomposed into at most $\lceil \frac{n }{2} \rceil$ paths. A graph is said to be an odd semi-clique if it can be obtained from a
Nevil Anto, Manu Basavaraju
doaj +1 more source
Bounds on the Twin-Width of Product Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 Twin-width is a graph width parameter recently introduced by Bonnet, Kim, Thomass\'{e} & Watrigant. Given two graphs $G$ and $H$ and a graph product $\star$, we address the question: is the twin-width of $G\star H$ bounded by a function of the twin ...
William Pettersson, John Sylvester
doaj +1 more source
A Study of $k$-dipath Colourings of Oriented Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 We examine $t$-colourings of oriented graphs in which, for a fixed integer $k \geq 1$, vertices joined by a directed path of length at most $k$ must be assigned different colours. A homomorphism model that extends the ideas of Sherk for the case $k=2$ is
Christopher Duffy +2 more
doaj +1 more source
Linear equations for unordered data vectors in $[D]^k\to{}Z^d$ [PDF]
Logical Methods in Computer Science, 2022 Following a recently considered generalisation of linear equations to unordered-data vectors and to ordered-data vectors, we perform a further generalisation to data vectors that are functions from k-element subsets of the unordered-data set to vectors ...
Piotr Hofman, Jakub Różycki
doaj +1 more source
Some theorems on passing from local to global presence of properties of functions [PDF]
Logical Methods in Computer Science, 2017 When given a class of functions and a finite collection of sets, one might be interested whether the class in question contains any function whose domain is a subset of the union of the sets of the given collection and whose restrictions to all of them ...
Dimiter Skordev
doaj +1 more source
An explicit construction of graphs of bounded degree that are far from being Hamiltonian [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Hamiltonian cycles in graphs were first studied in the 1850s. Since then, an impressive amount of research has been dedicated to identifying classes of graphs that allow Hamiltonian cycles, and to related questions.
Isolde Adler, Noleen Köhler
doaj +1 more source
On path-cycle decompositions of triangle-free graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 In this work, we study conditions for the existence of length-constrained path-cycle decompositions, that is, partitions of the edge set of a graph into paths and cycles of a given minimum length.
Andrea Jiménez, Yoshiko Wakabayashi
doaj +1 more source
Unique perfect matchings, forbidden transitions and proof nets for linear logic with Mix [PDF]
Logical Methods in Computer Science, 2020 This paper establishes a bridge between linear logic and mainstream graph theory, building on previous work by Retor\'e (2003). We show that the problem of correctness for MLL+Mix proof nets is equivalent to the problem of uniqueness of a perfect ...
Lê Thành Dũng Nguyên
doaj +1 more source
On Minimum Maximal Distance-k Matchings [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 We study the computational complexity of several problems connected with finding a maximal distance-$k$ matching of minimum cardinality or minimum weight in a given graph. We introduce the class of $k$-equimatchable graphs which is an edge analogue of $k$
Yury Kartynnik, Andrew Ryzhikov
doaj +1 more source