×

On the structure of (even hole, kite)-free graphs. (English) Zbl 1402.05065

Summary: A hole is an induced cycle with at least four vertices. A hole is even if it has an even number of vertices. Even-hole-free graphs are being actively studied in the literature. It is not known whether even-hole-free graphs can be optimally colored in polynomial time. A diamond is the graph obtained from the clique of four vertices by removing one edge. A kite is a graph consists of a diamond and another vertex adjacent to a vertex of degree two in the diamond. T. Kloks et al. [J. Comb. Theory, Ser. B 99, No. 5, 733–800 (2009; Zbl 1218.05160)] designed a polynomial-time algorithm to color an (even hole, diamond)-free graph. In this paper, we consider the class of (even hole, kite)-free graphs which generalizes (even hole, diamond)-free graphs. We prove that a connected (even hole, kite)-free graph is diamond-free, or the join of a clique and a diamond-free graph, or contains a clique cutset. This result, together with the result of T. Kloks et al. [loc. cit.], imply the existence of a polynomial time algorithm to color (even hole, kite)-free graphs. We also prove (even hole, kite)-free graphs are \(\beta \)-perfect in the sense of S. E. Markossian et al. [J. Comb. Theory, Ser. B 67, No. 1, 1–11 (1996; Zbl 0857.05038)]. Finally, we establish the Vizing bound for (even hole, kite)-free graphs.

MSC:

05C15 Coloring of graphs and hypergraphs
Full Text: DOI

References:

[1] Addario-Berry, L., Chudnovsky, M., Havet, F., Reed, B., Seymour, P.: 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
[2] Barnier, N., Brisset, P.: Graph coloring for air traffic flow management. Ann. Oper. Res. 130, 163-178 (2004) · Zbl 1062.90011 · doi:10.1023/B:ANOR.0000032574.01332.98
[3] Berge, C., Chvátal, V. (eds.): Topics on Perfect Graphs. North-Holland, Amsterdam (1984) · Zbl 0546.00006
[4] Cameron, K., Chaplick, S., Hoàng, C.T.: On the structure of (pan, even hole)-free graphs. August 12 (2015). arXiv:1508.03062 · Zbl 1387.05215
[5] Chang, H.-C., Lu, H.I.: A faster algorithm to recognize even-hole-free graphs. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms , pp. 1286-1297 (2012) · Zbl 1423.05129
[6] Chudnovsky, M., Kawarabayashi, K., Seymour, P.: Detecting even holes. J. Graph Theory 48, 85-111 (2005) · Zbl 1062.05135 · doi:10.1002/jgt.20040
[7] Conforti, M., Cornuéjols, G., Kapoor, A., Vušković, K.: Even-hole-free graphs, part I: decomposition theorem. J. Graph Theory 39, 6-49 (2002) · Zbl 1005.05034 · doi:10.1002/jgt.10006
[8] Conforti, M., Cornuéjols, G., Kapoor, A., Vušković, K.: Even-hole-free graphs, part II: recognition algorithm. J. Graph Theory 40, 238-266 (2002) · Zbl 1003.05095 · doi:10.1002/jgt.10045
[9] de Figueiredo, C.M.H., Vušković, K.: A class of \[\beta\] β perfect graphs. Discrete Math. 216, 169-193 (2000) · Zbl 0952.05028 · doi:10.1016/S0012-365X(99)00240-X
[10] Eisenblätter, A., Grötschel, M., Koster, A.M.C.A.: Frequency planning and ramifications of coloring. Discuss. Math. Graph Theory 22, 51-88 (2002) · Zbl 1055.05147 · doi:10.7151/dmgt.1158
[11] Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980) · Zbl 0541.05054
[12] Huang, S., da Silva, M.V.G.: A note on coloring (even-hole, cap)-free graphs October 30 (2015). arXiv:1510.09192
[13] Kloks, T., Mülcer, H., Vušković, K.: Even-hole-free graphs that do not contain diamonds: a structure theorem and its consequences. J. Combin. Theory B 99, 733-800 (2009) · Zbl 1218.05160 · doi:10.1016/j.jctb.2008.12.005
[14] Markossian, S.E., Gasparian, G.S., Reed, B.A.: \[ \beta\] β-Perfect graphs. J. Combin. Theory Ser. B 67, 1-11 (1996) · Zbl 0857.05038 · doi:10.1006/jctb.1996.0030
[15] Marx, D.: Graph Coloring problems and their applications in scheduling. Period. Polytech. Electr. Eng. 48, 11-16 (2004)
[16] Narayanan, L.: Channel assignment and graph multicoloring. In: Stojmenović, I. (ed.) Handbook of wireless networks and mobile computing, pp. 71-94. Wiley (2002). ISBN 9780471419020
[17] Tarjan, R.E.: Decomposition by clique separators. Discrete Math. 55, 221-232 (1985) · Zbl 0572.05039 · doi:10.1016/0012-365X(85)90051-2
[18] Vizing, V.G.: On an estimate of the chromatic class of p-graphs. Diskretn. Anal. 3, 25-30 (1964). (in Russian) · Zbl 1539.05042
[19] Whitesides, S. H.: A method for solving certain graph recognition and optimization problems, with applications to perfect graphs, in [3] · Zbl 0569.05043
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.