Abstrakt
Je-li dán graf G a jeho kostra T pateřní chromatické číslo, BBC(G,T), je definováno jako nejmenší k takové, že existuje obarvení c: V(G) -} {1, 2,..., k} splňující |c(u)-c(v)| }= 1, pokud uv je hrana G, a |c(u)-c(v)| }= 2, pokud uv je hrana T. Broersma a kol. [J.
Graph Theory, 55 (2007), pp. 137-152] položili otázku, zda existuje konstanta c taková, že pro každý graf G bez trojúhelníků s libolnou kostrou T platí nerovnost BBC(G, T) {= chi(G) c, kde chi(G) značí chromatické číslo. V článku ukazejeme, že taková konstanta neexistuje.
Zkonstruujeme grafy bez trojúhelníků R_n a jejich kostry T_n takové, že BBC(R_n, T_n) = 2 chi(R_n)-1 = 2n-1. Za účelem této konstrukce dostáváme také následující výsledek.
Pozměníme známou Mycielského konstrukci a získáme tak pro libovolné přirozené číslo n grafy bez trojúhelníků s chromatickým číslem n a dvojitým chromatickým číslem 2n (číslo 2 zde může být zobecněno).