A note on coloring (even-hole,cap)-free graphs
Huang, Shenwei · da Silva, Murilo V. G.
الأصل · EN
A hole is a chordless cycle of length at least four. A hole is even (resp. odd) if it contains an even (resp. odd) number of vertices. A cap is a graph induced by a hole with an additional vertex that is adjacent to exactly two adjacent vertices on the hole. In this note, we use a decomposition theorem by Conforti et al. (1999) to show that if a graph G does not contain any even hole or cap as an induced subgraph, then χ(G)≤ 3/2ω(G), where χ(G) and ω(G) are the chromatic number and the clique number of G, respectively. This bound is attained by odd holes and the Hajos graph. The proof leads to a polynomial-time 3/2-approximation algorithm for coloring (even-hole,cap)-free graphs.
الترجمة العربية
لا توجد ترجمة عربية لهذا البحث بعد. كن أوّل من يطلبها: تستغرق ثوانيَ معدودة، وتُحفظ النتيجة لكل قارئ قادم.