Branch-depth: Generalizing tree-depth of graphs

Cited 5 time in webofscience Cited 5 time in scopus
  • Hit : 549
  • Download : 270
DC FieldValueLanguage
dc.contributor.authorDeVos, Mattko
dc.contributor.authorKwon, O-joungko
dc.contributor.authorOum, Sang-ilko
dc.date.accessioned2020-09-28T02:55:10Z-
dc.date.available2020-09-28T02:55:10Z-
dc.date.created2020-09-23-
dc.date.issued2020-12-
dc.identifier.citationEUROPEAN JOURNAL OF COMBINATORICS, v.90-
dc.identifier.issn0195-6698-
dc.identifier.urihttp://hdl.handle.net/10203/276402-
dc.description.abstractWe present a concept called the branch-depth of a connectivity function, that generalizes the tree-depth of graphs. Then we prove two theorems showing that this concept aligns closely with the notions of tree-depth and shrub-depth of graphs as follows. For a graph G = (V, E) and a subset A of E we let lambda(G)(A) be the number of vertices incident with an edge in A and an edge in E \ A. For a subset X of V, let rho(G)(X) be the rank of the adjacency matrix between X and V \ X over the binary field. We prove that a class of graphs has bounded tree-depth if and only if the corresponding class of functions lambda(G) has bounded branch depth and similarly a class of graphs has bounded shrub-depth if and only if the corresponding class of functions rho(G) has bounded branch-depth, which we call the rank-depth of graphs. Furthermore we investigate various potential generalizations of tree-depth to matroids and prove that matroids representable over a fixed finite field having no large circuits are well-quasi ordered by restriction.-
dc.languageEnglish-
dc.publisherACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD-
dc.titleBranch-depth: Generalizing tree-depth of graphs-
dc.typeArticle-
dc.identifier.wosid000565160300001-
dc.identifier.scopusid2-s2.0-85087922057-
dc.type.rimsART-
dc.citation.volume90-
dc.citation.publicationnameEUROPEAN JOURNAL OF COMBINATORICS-
dc.identifier.doi10.1016/j.ejc.2020.103186-
dc.contributor.localauthorOum, Sang-il-
dc.contributor.nonIdAuthorDeVos, Matt-
dc.contributor.nonIdAuthorKwon, O-joung-
dc.description.isOpenAccessY-
dc.type.journalArticleArticle-
dc.subject.keywordPlusMONADIC 2ND-ORDER LOGIC-
dc.subject.keywordPlusRANK-WIDTH-
dc.subject.keywordPlusMINORS-
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 5 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0