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 -