Structure and algorithms for (cap,even hole)-free graphs |
| |
Authors: | Kathie Cameron Murilo V.G. da Silva Shenwei Huang Kristina Vušković |
| |
Affiliation: | 1. Department of Mathematics, Wilfrid Laurier University, Waterloo, ON, Canada, N2L 3C5;2. Department of Computer Science, Federal University of Technology-Paraná, Curitiba, Brazil;3. School of Computer Science and Engineering, University of New South Wales, Sydney, NSW 2052, Australia;4. School of Computing, University of Leeds, Leeds LS2 9JT, UK;5. Faculty of Computer Science (RAF), Union University, Knez Mihajlova 6/VI, 11000 Belgrade, Serbia |
| |
Abstract: | A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this paper, we consider (cap, even hole)-free graphs, and more generally, (cap, 4-hole)-free odd-signable graphs. We give an explicit construction of these graphs. We prove that every such graph has a vertex of degree at most , and hence , where denotes the size of a largest clique in and denotes the chromatic number of . We give an algorithm for -coloring these graphs for fixed and an algorithm for maximum weight stable set, where is the number of vertices and is the number of edges of the input graph. We also give a polynomial-time algorithm for minimum coloring.Our algorithms are based on our results that triangle-free odd-signable graphs have treewidth at most 5 and thus have clique-width at most 48, and that (cap, 4-hole)-free odd-signable graphs without clique cutsets have treewidth at most and clique-width at most 48. |
| |
Keywords: | Even-hole-free graph Structure theorem Decomposition Combinatorial optimization Coloring Maximum weight stable set Treewidth Clique-width |
本文献已被 ScienceDirect 等数据库收录! |
|