การให้สีแบบเท่าเทียมในกราฟบางประเภท
ชื่อผู้แต่งข้างต้นเป็นข้อความจากระเบียนผลงาน ไม่ได้ผูกกับรหัสนักวิจัย จึงกดดูผลงานอื่นของบุคคลนี้ไม่ได้ — ในคลังนี้ 142,080 ผลงาน (63.6% ของทั้งหมด) มีชื่อผู้แต่งที่เชื่อมกับหน้าผู้แต่งได้ และ 60,298 ผลงาน (27.0%) มีผู้แต่งที่ผูกกับรหัสนักวิจัยจริง ส่วนอีก 81,382 ผลงานไม่มีข้อมูลผู้แต่งเลย (มีชื่อผู้แต่งเป็นข้อความอยู่ 142,009 ผลงาน = 63.5%)
บทคัดย่อ
รงคดัชนีแบบเข้ม s'(G) ของกราฟหลายเชิง G คือจำนวนเต็ม k ที่น้อยที่สุดซึ่งสามารถให้สีเส้นเชื่อมในกราฟ G ได้ด้วยสี k สี โดยที่จุดยอดในแต่ละคลาสของสีก่อให้เกิดการจับคู่แบบอินดิวซ์ ให้ I(G) คือสับดิวิชันของกราฟหลายเชิง G ซึ่งแต่ละเส้นเชื่อมถูกสับดิวิชันเพียงหนึ่งครั้งเท่านั้น Brualdi และ Massey [R.A. Brualdi and J.Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math., 122 (1993), 51-58] ได้พิสูจน์ว่า s'(I(G))<= 2 \Delta (G) สำหรับทุกกราฟเชิงเดียว G ให้ F_D แทน กราฟที่ได้จากวงขนาด 5 โดยการเพิ่มจุดยอดจำนวน D-2 จุด และเชื่อมจุดยอดดังกล่าวกับจุดยอดสองจุดใด ๆ ในวงขนาด 5 ซึ่งไม่มีเส้นเชื่อมกัน Wu และ Lin [J. Wu and W. Lin, The strong chromatic index of a class of graphs, Discrete Math. 308 (2008), 6254-6261] ได้พิสูจน์ว่า ถ้า G เป็นกราฟหลายเชิงซึ่งไม่มีวงวนที่ไม่ใช่ F_3 และ d(x)+d(y) <= 5 สำหรับทุกเส้นเชื่อม xy ของกราฟ G แล้ว s'(G) <= 6 ซึ่งผลลัพธ์นี้เป็นการตอบคำถามเปิดที่นำเสนอโดย Faudree และคณะ ในงานวิจัยนี้ เราแสดงรูปแบบที่ดีกว่าของผลลัพธ์ทั้งสองที่กล่าวมา โดยพิสูจน์ว่า ถ้า G เป็นกราฟหลายเชิงซึ่งไม่มีวงวนและมี d(x)+d(y) <= D+2 โดยที่ min{d(x), d(y)} <= 2 สำหรับทุกเส้นเชื่อม xy ของกราฟ G และ G ไม่ใช่กราฟ F_D แล้ว s'(G) <= 2D สิ่งที่ได้ตามมาคือ s'(I(G)) <= 2 \Delta(G) สำหรับทุกกราฟหลายเชิง G ยิ่งไปกว่านั้น ได้ว่า s'(H) <= 2 \Delta(G) สำหรับทุกสับดิวิชัน H ของ I(G) ยกเว้นกรณี G=F_{\Delta (G)}