On the structure of (pan, even hole)-free graphs. (English) Zbl 1387.05215
Summary: A hole is a chordless cycle with at least four vertices. A pan is a graph that consists of a hole and a single vertex with precisely one neighbor on the hole. An even hole is a hole with an even number of vertices. We prove that a (pan, even hole)-free graph can be decomposed by clique cutsets into essentially unit circular-arc graphs. This structure theorem is the basis of our \(O(nm)\)-time certifying algorithm for recognizing (pan, even hole)-free graphs and for our \(O(n^{2.5}+nm)\)-time algorithm to optimally color them. Using this structure theorem, we show that the tree-width of a (pan, even hole)-free graph is at most 1.5 times the clique number minus 1, and thus the chromatic number is at most 1.5 time the clique number.
MSC:
| 05C75 | Structural characterization of families of graphs |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68W40 | Analysis of algorithms |
References:
| [1] | P. Aboulker; P. Charbit; N. Trotignon; K. Vušković, Vertex elimination orderings for hereditary graph classes, Discrete Math, 338, 825-834, (2015) · Zbl 1306.05202 · doi:10.1016/j.disc.2014.12.014 |
| [2] | L. Addario-Berry; M. Chudnovsky; F. Havet; B. Reed; P. Seymour, Bisimplicial vertices in even-hole-free graphs, J. Comb. Theory Ser. B, 98, 1119-1164, (2008) · Zbl 1205.05119 · doi:10.1016/j.jctb.2007.12.006 |
| [3] | (1984) |
| [4] | A. Brandstat; V. Lozin; R. Mosca, Independent sets of maximum weight in pan-free graphs, SIAM J. Discrete Math, 34, 239-254, (2010) · Zbl 1211.68281 · doi:10.1137/090750822 |
| [5] | P. Buneman, A characterization of rigid circuit graphs, Discrete Math, 9, 205-212, (1974) · Zbl 0288.05128 · doi:10.1016/0012-365X(74)90002-8 |
| [6] | K. Cameron; E. Eschen; C. T. Hoàng; R. Sritharan, 97-108, (2007) · Zbl 1114.05043 · doi:10.1007/978-3-7643-7400-6_9 |
| [7] | H.-C. Chang; H. I. Lu, A faster algorithm to recognize even-hole-free graphs, J. Combin. Theory Ser. B, 113, 141-161, (2015) · Zbl 1315.05107 · doi:10.1016/j.jctb.2015.02.001 |
| [8] | M. Chudnovsky; K. Kawarabayashi; P. Seymour, Detecting even holes, J. Graph Theory, 48, 85-111, (2005) · Zbl 1062.05135 |
| [9] | M. Conforti; G. Cornuejols; A. Kapoor; K. Vušković, Even-hole-free graphs part II: Recognition algorithm, J. Graph Theory, 40, 238-266, (2002) · Zbl 1003.05095 |
| [10] | D. G. Corneil; U. Rotics, On the relationship between clique-width and treewidth, SIAM J. Comput, 34, 825-847, (2005) · Zbl 1069.05067 · doi:10.1137/S0097539701385351 |
| [11] | B. Courcelle; J. A. Makowsky; U. Rotics, Linear time solvable optimization problems on graphs of bounded clique width, Theory Comput. Syst, 33, 125-150, (2000) · Zbl 1009.68102 · doi:10.1007/s002249910009 |
| [12] | B. Courcelle; S. Olariu, Upper bounds to the clique-width of a graph, Discrete Appl. Math, 101, 77-114, (2000) · Zbl 0958.05105 · doi:10.1016/S0166-218X(99)00184-5 |
| [13] | M. V. G. da Silva; K. Vušković, Triangulated neighborhoods in even-hiole-free graphs, Discrete Math, 307, 1065-1073, (2007) · Zbl 1115.05078 · doi:10.1016/j.disc.2006.07.027 |
| [14] | G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, 71-76, (1961) · Zbl 0098.14703 · doi:10.1007/BF02992776 |
| [15] | C. De Simone, On the vertex packing problem, Graphs Combin, 9, 19-30, (1993) · Zbl 0781.05041 · doi:10.1007/BF01195324 |
| [16] | F. Gavril, The intersection graphs of subtrees of trees are exactly the chordal graphs, J. Combin. Theory Ser. B, 16, 47-56, (1974) · Zbl 0266.05101 · doi:10.1016/0095-8956(74)90094-X |
| [17] | F. Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. Comput, 1, 180-187, (1972) · Zbl 0227.05116 · doi:10.1137/0201013 |
| [18] | M. C. Golumbic, (1980) |
| [19] | I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput, 10, 718-720, (1981) · Zbl 0473.68034 · doi:10.1137/0210055 |
| [20] | T. Kloks; D. Kratsch; H. Müller, Finding and counting small induced subgraphs efficiently, Inform. Proc. Lett, 74, 115-121, (2000) · Zbl 1339.05394 · doi:10.1016/S0020-0190(00)00047-8 |
| [21] | T. Kloks; H. Müller; K. Vušković, Even-hole-free graphs that do not contain diamonds: a structure theorem and its consequences, J. Combin. Theory Ser. B, 99, 733-800, (2009) · Zbl 1218.05160 · doi:10.1016/j.jctb.2008.12.005 |
| [22] | D. Kobler; U. Rotics, Edge dominating set and colorings on graphs with fixed clique-width, Discrete Appl. Math, 126, 197-221, (2003) · Zbl 1009.05103 · doi:10.1016/S0166-218X(02)00198-1 |
| [23] | J. Kratochvil; D. Kral; Zs. Tuza; G. J. Woeginger, 254-262, (2001) |
| [24] | M. C. Lin; J. L. Szwarcfiter, Unit circular-arc representations and feasible circulations, SIAM J. Discrete Math, 22, 409-423, (2008) · Zbl 1232.05145 · doi:10.1137/060650805 |
| [25] | J. A. Makowsky; U. Rotics, On the clique-width of graphs with few \(P\_{}\{4\}\), Int. J. Found. Comput. Sci, 10, 329-348, (1999) · Zbl 1320.05096 · doi:10.1142/S0129054199000241 |
| [26] | S. E. Markossian; G. S. Gasparian; B. A. Reed, β-perfect graphs, J. Combin. Theory Ser. B, 67, 1-11, (1996) · Zbl 0857.05038 · doi:10.1006/jctb.1996.0030 |
| [27] | S. Olariu, The strong perfect graph conjecture for pan-free graphs, J. Combin. Theory B, 47, 187-191, (1989) · Zbl 0661.05057 · doi:10.1016/0095-8956(89)90019-1 |
| [28] | J. B. Orlin; M. A. Bonuccelli; D. P. Bovet, An · Zbl 0496.68047 · doi:10.1137/0602012 |
| [29] | S.-I. Oum, Approximating rank-width and clique-width quickly, ACM Trans. Algorithms, 5, (2009) · Zbl 1126.05304 |
| [30] | B. A. Reed, 85-107, (2003) · Zbl 1035.05090 |
| [31] | W. K. Shih; W. L. Hsu, An · Zbl 0682.68062 · doi:10.1016/0166-218X(89)90011-5 |
| [32] | R. E. Tarjan; M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput, 13, 566-579, (1984) · Zbl 0545.68062 · doi:10.1137/0213035 |
| [33] | R. E. Tarjan, Decomposition by clique separators, Discrete Math, 55, 221-232, (1985) · Zbl 0572.05039 · doi:10.1016/0012-365X(85)90051-2 |
| [34] | K. Vušković, Even-hole-free graphs: A survey, Appl. Anal. Discrete Math, 4, 219-240, (2010) · Zbl 1265.05518 · doi:10.2298/AADM100812027V |
| [35] | S. H. Whitesides, 88, 281-297, (1984) |
| [36] | J. R. Walter, Representations of chordal graphs as subtrees of a tree, J. Graph Theory, 2, 265-267, (1978) · Zbl 0441.05022 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
