TY - JOUR

T1 - Substitution and χ-boundedness

AU - Chudnovsky, Maria

AU - Penev, Irena

AU - Scott, Alex

AU - Trotignon, Nicolas

N1 - Funding Information:
E-mail addresses: [email protected] (M. Chudnovsky), [email protected] (I. Penev), [email protected] (A. Scott), [email protected] (N. Trotignon). 1 Partially supported by NSF grants DMS-0758364 and DMS-1001091. 2 This research was conducted while the author was a graduate student at Columbia University. 3 Partially supported by the French Agence Nationale de la Recherche under reference anr-10-jcjc-Heredia.

PY - 2013/9

Y1 - 2013/9

N2 - A class G of graphs is said to be χ. bounded if there is a function f:N→R such that for all G∈G and all induced subgraphs H of G, χ(H). ≤. f(ω(H)). In this paper, we show that if G is a χ-bounded class, then so is the closure of G under any one of the following three operations: substitution, gluing along a clique, and gluing along a bounded number of vertices. Furthermore, if G is χ-bounded by a polynomial (respectively: exponential) function, then the closure of G under substitution is also χ-bounded by some polynomial (respectively: exponential) function. In addition, we show that if G is a χ-bounded class, then the closure of G under the operations of gluing along a clique and gluing along a bounded number of vertices together is also χ-bounded, as is the closure of G under the operations of substitution and gluing along a clique together.

AB - A class G of graphs is said to be χ. bounded if there is a function f:N→R such that for all G∈G and all induced subgraphs H of G, χ(H). ≤. f(ω(H)). In this paper, we show that if G is a χ-bounded class, then so is the closure of G under any one of the following three operations: substitution, gluing along a clique, and gluing along a bounded number of vertices. Furthermore, if G is χ-bounded by a polynomial (respectively: exponential) function, then the closure of G under substitution is also χ-bounded by some polynomial (respectively: exponential) function. In addition, we show that if G is a χ-bounded class, then the closure of G under the operations of gluing along a clique and gluing along a bounded number of vertices together is also χ-bounded, as is the closure of G under the operations of substitution and gluing along a clique together.

KW - Coloring

KW - Connectivity

KW - Graph operations

KW - Homogeneous set

KW - Substitution

KW - χ-bounded

UR - http://www.scopus.com/inward/record.url?scp=84883558872&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883558872&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2013.02.004

DO - 10.1016/j.jctb.2013.02.004

M3 - Article

AN - SCOPUS:84883558872

SN - 0095-8956

VL - 103

SP - 567

EP - 586

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 5

ER -