ในทฤษฎีกราฟการระบายสีแบบอ่อน (weak coloring ) เป็นกรณีพิเศษของการติดป้ายกราฟ (graph labeling ) การระบายสีแบบอ่อนk สี (weak k-coloring) ของกราฟG = ( V ,  E )จะกำหนดสีc ( v ) ∈ {1, 2, ..., k } ให้กับแต่ละจุดยอดv ∈ Vโดยที่แต่ละจุดยอดที่ไม่โดดเดี่ยว จะต้องอยู่ติดกับจุดยอดที่มีสีต่างกันอย่างน้อยหนึ่งจุด ในสัญลักษณ์ สำหรับแต่ละจุดยอดที่ไม่โดดเดี่ยวv ∈ Vจะมีจุดยอดu ∈ Vที่มี{ u , v } ∈ Eและc ( u ) ≠ c ( v )

รูปทางด้านขวาแสดงการระบายสีแบบ 2 สีอ่อนของกราฟ โดยแต่ละจุดยอดสีเข้ม (สี 1) จะอยู่ติดกับจุดยอดสีอ่อน (สี 2) อย่างน้อยหนึ่งจุด และในทางกลับกัน

การระบายสีจุดยอดของกราฟเป็นการระบายสีแบบอ่อน แต่ในทางกลับกันนั้นไม่จำเป็นเสมอไป

กราฟทุกกราฟมีการระบายสีแบบอ่อน 2 สี รูปทางด้านขวาแสดงอัลกอริทึมอย่างง่ายสำหรับการสร้างการระบายสีแบบอ่อน 2 สีในกราฟใดๆ ส่วน (a) แสดงกราฟดั้งเดิม ส่วน (b) แสดง ต้นไม้ ค้นหาแบบกว้างของกราฟเดียวกัน ส่วน (c) แสดงวิธีการระบายสีต้นไม้: เริ่มจากราก ชั้นต่างๆ ของต้นไม้จะถูกระบายสีสลับกันด้วยสี 1 (เข้ม) และสี 2 (อ่อน)

ถ้าไม่มีจุดยอดโดดเดี่ยวในกราฟGการระบายสีแบบ 2 สีแบบอ่อนจะกำหนดการแบ่งส่วนแบบโดมิแนนท์ : เซตของโหนดที่มีc ( v ) = 1เป็นเซตครอบงำและเซตของโหนดที่มีc ( v ) = 2เป็นเซตครอบงำอีกเซตหนึ่ง

ในอดีต การระบายสีแบบอ่อนทำหน้าที่เป็นตัวอย่างแรกของปัญหากราฟที่ไม่ธรรมดาซึ่งสามารถแก้ไขได้ด้วยอัลกอริทึมแบบโลคอล ( อัลกอริทึมแบบกระจายที่ทำงานในรอบการสื่อสารแบบซิงโครนัสจำนวนคงที่) กล่าวคือ หากดีกรีของแต่ละโหนดเป็นเลขคี่และถูกจำกัดด้วยค่าคงที่ จะมีอัลกอริทึมแบบกระจายที่มีเวลาคงที่สำหรับการระบายสีแบบอ่อน 2 สี^{[ 1 ]}

สิ่งนี้แตกต่างจากการระบายสีจุดยอด (ที่ไม่ใช่แบบอ่อน) : ไม่มีอัลกอริทึมแบบกระจายที่มีเวลาคงที่สำหรับการระบายสีจุดยอด อัลกอริทึมที่ดีที่สุดที่เป็นไปได้ (สำหรับการค้นหาการระบายสีขั้นต่ำ แต่ไม่จำเป็นต้องเป็นการระบายสีขั้นต่ำ) ต้องใช้รอบการสื่อสารO ( log * | V |) ^{[ 1 ] [ 2 ] [ 3 ]}โดย ที่log * xคือลอการิทึมแบบวนซ้ำของ  x