Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 3

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  interval graph
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs

100%
Immel P., Wenger P. S.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
165-174
EN
A distinguishing coloring of a graph G is a coloring of the vertices so that every nontrivial automorphism of G maps some vertex to a vertex with a different color. The distinguishing number of G is the minimum k such that G has a distinguishing coloring where each vertex is assigned a color from {1, . . . , k}. A list assignment to G is an assignment L = {L(v)}v∈V (G) of lists of colors to the vertices of G. A distinguishing L-coloring of G is a distinguishing coloring of G where the color of each vertex v comes from L(v). The list distinguishing number of G is the minimum k such that every list assignment to G in which |L(v)| = k for all v ∈ V (G) yields a distinguishing L-coloring of G. We prove that if G is an interval graph, then its distinguishing number and list distinguishing number are equal.
2
Content available remote

A Characterization of 2-Tree Probe Interval Graphs

100%
Brown D. E., Flesch B. M., Richard J.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
509-527
EN
A graph is a probe interval graph if its vertices correspond to some set of intervals of the real line and can be partitioned into sets P and N so that vertices are adjacent if and only if their corresponding intervals intersect and at least one belongs to P. We characterize the 2-trees which are probe interval graphs and extend a list of forbidden induced subgraphs for such graphs created by Pržulj and Corneil in [2-tree probe interval graphs have a large obstruction set, Discrete Appl. Math. 150 (2005) 216-231]
3
Content available remote

The Phylogeny Graphs of Doubly Partial Orders

100%
Park B., Sano Y.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 4
657-664
EN
The competition graph of a doubly partial order is known to be an interval graph. The CCE graph and the niche graph of a doubly partial order are also known to be interval graphs if the graphs do not contain a cycle of length four and three as an induced subgraph, respectively. Phylogeny graphs are variant of competition graphs. The phylogeny graph P(D) of a digraph D is the (simple undirected) graph defined by V (P(D)) := V (D) and E(P(D)) := {xy | N+D (x) ∩ N+D(y) ¹ ⊘ } ⋃ {xy | (x,y) ∈ A(D)}, where N+D(x):= {v ∈ V(D) | (x,v) ∈ A (D)}. In this note, we show that the phylogeny graph of a doubly partial order is an interval graph. We also show that, for any interval graph G̃, there exists an interval graph G such that G̃ contains the graph G as an induced subgraph and that G̃ is the phylogeny graph of a doubly partial order.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.