We study graph classes modeled by families of non-crossing (NC) connected sets. Two classic graph classes in this context are disk graphs and proper interval graphs. We focus on the cases when the ...sets are paths and the host is a tree (generalizing proper interval graphs). Forbidden induced subgraph characterizations and linear time certifying recognition algorithms are given for intersection graphs of NC paths of a tree (and related subclasses). Consequently, we obtain a linear time algorithm to detect the presence/absence of an induced claw (K1,3) in a chordal graph.
For the intersection graphs of NC paths of a tree, we study dominating sets and spanning subgraphs. For example, minimum connected dominating sets are characterized (leading to a linear time algorithm to compute one), and we observe that there is always an independent dominating set which is a minimum dominating set (again leading to linear time algorithms for these). Regarding spanning subgraphs, each such graph G is shown to have a Hamiltonian cycle if it is 2-connected, and when G is not 2-connected, a minimum-leaf spanning tree of G has ℓ leaves if G's block-cutpoint tree has exactly ℓ leaves (e.g., implying that the block-cutpoint tree is a path if and only if the graph has a Hamiltonian path).
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
In this paper we consider the problem of listing the maximal k-degenerate induced subgraphs of a chordal graph, and propose an output-sensitive algorithm using delay O(m⋅ω(G)) for any n-vertex ...chordal graph with m edges, where ω(G)≤n is the maximum size of a clique in G. Degeneracy is a well known sparsity measure, and k-degenerate subgraphs are a notion of sparse subgraphs, which generalizes other problems such as independent sets (0-degenerate subgraphs) and forests (1-degenerate subgraphs).
Many efficient enumeration algorithms are designed by solving the so-called Extension problem, which asks whether there exists a maximal solution containing a given set of nodes, but no node from a forbidden set. We show that solving this problem is np-complete for maximal k-degenerate induced subgraphs, motivating the need for additional techniques.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
An asteroidal triple in a graph G is a set of three non-adjacent vertices such that for any two of them there exists a path between them that does not intersect the neighborhood of the third. A ...special asteroidal triple in a graph G is an asteroidal triple such that each pair is linked by a special connection. A special asteroidal triple play a central role in a characterization of directed path graphs by Cameron, Hoáng and Lévêque. They also introduce a related notion of asteroidal quadruple and conjecture a characterization of rooted path graphs. In this original form this conjecture is not complete, still in leafage four, as was showed in M. Gutierrez, B. Lévêque, S. B. Tondato, Asteroidal quadruples in non rooted path graphs, manuscript 2012. but as suggested by the conjecture, a characterization by forbidding particular type of asteroidal quadruples may holds. We prove that the conjecture in the original form is true on directed path graphs with leafage four having two minimal separators with multiplicity two. Thus we build the family of forbidden for this case.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
End Simplicial Vertices in Path Graphs Gutierrez, Marisa; Tondato, Silvia B.
Discussiones Mathematicae. Graph Theory,
05/2016, Volume:
36, Issue:
2
Journal Article
Peer reviewed
Open access
A graph is a path graph if there is a tree, called UV -model, whose vertices are the maximal cliques of the graph and for each vertex x of the graph the set of maximal cliques that contains it ...induces a path in the tree. A graph is an interval graph if there is a UV -model that is a path, called an interval model. Gimbel 3 characterized those vertices in interval graphs for which there is some interval model where the interval corresponding to those vertices is an end interval. In this work, we give a characterization of those simplicial vertices x in path graphs for which there is some UV -model where the maximal clique containing x is a leaf in this UV -model.
Full text
Available for:
IZUM, KILJ, NUK, PILJ, PNG, SAZU, UL, UM, UPUK
A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted directed path graph is the intersection graph of a family of directed subpaths of a ...rooted tree. Clearly, rooted directed path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted directed path graphs. With the purpose of proving knowledge in this direction, we show in this paper properties of directed path models that can not be rooted for chordal graphs with any leafage and with leafage four. Therefore, we prove that for leafage four directed path graphs minimally non rooted directed path graphs have a unique asteroidal quadruple, and can be characterized by the presence of certain type of asteroidal quadruples.
Full text
Available for:
DOBA, EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, IZUM, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UILJ, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
Asteroidal Quadruples in non Rooted Path Graphs Gutierrez, Marisa; Lévêque, Benjamin; Tondato, Silvia B.
Discussiones Mathematicae. Graph Theory,
01/2015, Volume:
35, Issue:
4
Journal Article
Peer reviewed
Open access
A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted path graph is the intersection graph of a family of directed subpaths of a rooted tree. ...Rooted path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted path graphs. For this purpose, we are studying in this paper directed path graphs that are non rooted path graphs. We prove that such graphs always contain an asteroidal quadruple.
Full text
Available for:
IZUM, KILJ, NUK, PILJ, PNG, SAZU, UL, UM, UPUK
We deal with some generalizations of the graph coloring problem on classes of perfect graphs. Namely we consider the μ-coloring problem (upper bounds for the color on each vertex), the precoloring ...extension problem (a subset of vertices colored beforehand), and a problem generalizing both of them, the (γ,μ)-coloring problem (lower and upper bounds for the color on each vertex). We characterize the complexity of all those problems on clique-trees of different heights, providing polynomial-time algorithms for the cases that are easy. These results have interesting corollaries. First, one can observe on clique-trees of different heights the increasing complexity of the chain k-coloring, μ-coloring, (γ,μ)-coloring, and list-coloring. Second, clique-trees of height 2 are the first known example of a class of graphs where μ-coloring is polynomial-time solvable and precoloring extension is NP-complete, thus being at the same time the first example where μ-coloring is polynomially solvable and (γ,μ)-coloring is NP-complete. Last, we show that theμ-coloring problem on unit interval graphs is NP-complete. These results answer three questions from Bonomo et al. F. Bonomo, G. Durán, J. Marenco, Exploring the complexity boundary between coloring and list-coloring, Annals of Operations Research 169 (1) (2009) 3–16.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
We show complexity results for some generalizations of the graph coloring problem on two classes of perfect graphs, namely clique trees and unit interval graphs. We deal with the
μ-coloring problem ...(upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand), and a problem generalizing both of them, the (
γ,
μ)-coloring problem (lower and upper bounds for the color on each vertex). We characterize the complexity of all those problems on clique trees of different heights, providing polytime algorithms for the cases that are easy. These results have two interesting corollaries: first, one can observe on clique trees of different heights the increasing complexity of the chain k-coloring,
μ-coloring, (
γ,
μ)-coloring, list-coloring. Second, clique trees of height 2 are the first known example of a class of graphs where
μ-coloring is polynomial time solvable and precoloring extension is NP-complete, thus being at the same time the first example where
μ-coloring is polynomially solvable and (
γ,
μ)-coloring is NP-complete. Last, we show that the
μ-coloring problem on unit interval graphs is NP-complete. These results answer three questions from Ann. Oper. Res. 169(1) (2009), 3–16.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
We present the first dynamic algorithm that maintains a clique tree representation of a chordal graph and supports the following operations: (1) query whether deleting or inserting an arbitrary edge ...preserves chordality; and (2) delete or insert an arbitrary edge, provided it preserves chordality. We give two implementations. In the first, each operation runs in
O
(
n
) time, where
n
is the number of vertices. In the second, an insertion query runs in
O
(log
2
n
) time, an insertion in
O
(
n
) time, a deletion query in
O
(
n
) time, and a deletion in
O
(
n
log
n
) time. We also present a data structure that allows a deletion query to run in
O
(√m) time in either implementation, where
m
is the current number of edges. Updating this data structure after a deletion or insertion requires
O
(
m
) time.
We also present a very simple dynamic algorithm that supports each of the following operations in
O
(1) time on a general graph: (1) query whether the graph is split, and (2) delete or insert an arbitrary edge.
PDF
