Triangle-Free Graphs

In Chap. 12 we proved that graphs with girth at least 5, i.e. graphs with no triangles or 4-cycles, have chromatic number at most % MathType!MTEF!2!1!+- % feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaaeaaaaaaaaa8 % qacaWGpbGaaiikamaalaaapaqaa8qacqqHuoara8aabaWdbiaadMea % caWGUbGaeuiLdqeaaiaacMcacaGGUaaaaa!3DCE!]]</EquationSource><EquationSource Format="TEX"><![CDATA[$$O(\frac{\Delta }{{In\Delta }}).$$ In this chapter, we will present Johansson’s stronger result [86] that the same bound holds even for triangle-free graphs.