Precoloring extension. II. Graphs classes related to bipartite graphs.
Game list colouring of graphs.
Stronger bounds for generalized degrees and Menger path systems
For positive integers d and m, let denote the property that between each pair of vertices of the graph G, there are m internally vertex disjoint paths of length at most d. For a positive integer t a graph G satisfies the minimum generalized degree condition δₜ(G) ≥ s if the cardinality of the union of the neighborhoods of each set of t vertices of G is at least s. Generalized degree conditions that ensure that is satisfied have been investigated. In particular, it has been shown, for fixed positive...
Paths through fixed vertices in edge-colored graphs
We study the problem of finding an alternating path having given endpoints and passing through a given set of vertices in edge-colored graphs (a path is alternating if any two consecutive edges are in different colors). In particular, we show that this problem in NP-complete for 2-edge-colored graphs. Then we give a polynomial characterization when we restrict ourselves to 2-edge-colored complete graphs. We also investigate on (s,t)-paths through fixed vertices, i.e. paths of length s+t such that...
Page 1