Buscar
Mostrando ítems 1-10 de 33
A Note on Total and List Edge-Colouring of Graphs of Tree-Width 3
(Springer, 2016)
It is shown that Halin graphs are -edge-choosable and that graphs of tree-width 3 are -edge-choosable and -total-colourable.
Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
(ELSEVIER SCIENCE BV, 2009)
Let M = (V, E, A) be a mixed graph with vertex set V, edge set E and arc set A. A cycle cover of M is a family C = {C(1), ... , C(k)} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The ...
List Edge-Coloring and Total Coloring in Graphs of Low Treewidth
(Wiley & Sons, 2016)
We prove that the list chromatic index of a graph of maximum degree Delta and treewidth <= root 2 Delta -3 is Delta; and that the total chromatic number of a graph of maximum degree and treewidth <= Delta/3+1 is Delta+1. ...
Colouring exact distance graphs of chordal graphs
(Elsevier, 2020)
For a graph G = (V, E) and positive integer p, the exact distance-p graph G([hp]) is the graph with vertex set V and with an edge between vertices x and y if and only if x and y have distance p. Recently, there has been ...
The complexity of reverse engineering problems for conjunctive queries
(Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017)
Reverse engineering problems for conjunctive queries (CQs), such as query by example (QBE) ordefinability, take a set of user examples and convert them into an explanatory CQ. Despite theirimportance, the complexity of ...
On distance-preserving elimination orderings in graphs: complexity and algorithms
(Elsevier, 2018-07-10)
For every connected graph G, a subgraph H of G is isometric if the distance between any two vertices in H is the same in H as in G. A distance-preserving elimination ordering of G is a total ordering of its vertex-set V ...
k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth.
Cops and robber games, introduced by Winkler and Nowakowski (in Discrete Math. 43(2–3), 235–239, 1983) and independently defined by Quilliot (in J. Comb. Theory, Ser. B 38(1), 89–92, 1985), concern a team of cops that must ...