Markov bases of binary graph models of K-4-minor free graphs

KRÁĽ, Daniel; S NORINE a O PANGRAC. Markov bases of binary graph models of K-4-minor free graphs. Journal of Combinatorial Theory, Series A. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2010, roč. 117, č. 6, s. 759-765. ISSN 0097-3165. Dostupné z: https://doi.org/10.1016/j.jcta.2009.07.007.

Základní údaje

Originální název

Markov bases of binary graph models of K-4-minor free graphs

Autoři

KRÁĽ, Daniel; S NORINE a O PANGRAC

Vydání

Journal of Combinatorial Theory, Series A, SAN DIEGO, ACADEMIC PRESS INC ELSEVIER SCIENCE, 2010, 0097-3165

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.683

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.1016/j.jcta.2009.07.007

UT WoS

000278875200010

Klíčová slova anglicky

Binary graph model; Markov base; Markov width; Series-parallel graphs

---

Anotace

V originále

The Markov width of a graph is a graph invariant defined as the maximum degree of a Markov basis element for the corresponding graph model for binary contingency tables. We show that a graph has Markov width at most four if and only if it contains no K-4 as a minor, answering a question of Develin and Sullivant. We also present a lower bound of order Omega(n(2-epsilon)) on the Markov width of K-n. (C) 2009 Elsevier Inc. All rights reserved.