A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs

Yair Caro; Juan Rojas; Sergio Ruiz

Czechoslovak Mathematical Journal (1996)

  • Volume: 46, Issue: 3, page 413-419
  • ISSN: 0011-4642

How to cite

top

Caro, Yair, Rojas, Juan, and Ruiz, Sergio. "A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs." Czechoslovak Mathematical Journal 46.3 (1996): 413-419. <http://eudml.org/doc/30320>.

@article{Caro1996,
author = {Caro, Yair, Rojas, Juan, Ruiz, Sergio},
journal = {Czechoslovak Mathematical Journal},
keywords = {decompositions; factors; decomposable graphs; forbidden subgraph characterization},
language = {eng},
number = {3},
pages = {413-419},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs},
url = {http://eudml.org/doc/30320},
volume = {46},
year = {1996},
}

TY - JOUR
AU - Caro, Yair
AU - Rojas, Juan
AU - Ruiz, Sergio
TI - A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs
JO - Czechoslovak Mathematical Journal
PY - 1996
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 46
IS - 3
SP - 413
EP - 419
LA - eng
KW - decompositions; factors; decomposable graphs; forbidden subgraph characterization
UR - http://eudml.org/doc/30320
ER -

References

top
  1. Randomly star-decomposable graphs, Congressus Numeratium 64 (1988), 193–195. (1988) MR0988681
  2. Random Packings of Graphs, Manuscript, . 
  3. An O ( n 2 . 5 ) algorithm for maximum matching in general graphs, Proc. 16th Annual Symp. on Foundation of Computer Sciences. IEEE, New York (1975), 100–112. (1975) MR0428780
  4. [unknown], Journal of Graph Theory 1, 9 (1985), . (1985) Zbl1170.01303
  5. 10.1016/0012-365X(85)90161-X, Discrete Mathematics 57 (1985), 123–128. (1985) Zbl0588.05035MR0816053DOI10.1016/0012-365X(85)90161-X
  6. 10.1002/jgt.3190030209, Journal of Graph Theory 3 (1979), 183–186. (1979) Zbl0404.05053MR0530304DOI10.1002/jgt.3190030209
  7. Graph Decomposition is NPC, a Complete Proof of Holyer’s Conjecture, (to appear). (to appear) 

NotesEmbed ?

top

You must be logged in to post comments.