×

The clique-perfectness and clique-coloring of outer-planar graphs. (English) Zbl 1431.90134

Summary: A clique is defined as a complete subgraph maximal under inclusion and having at least two vertices. A clique-transversal of a graph \(G\) is a subset of vertices that meets all the cliques of \(G\). A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph \(G\) is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of \(G\). An open problem concerning clique-perfect graphs is to find all minimal forbidden induced subgraphs of clique-perfect graphs. A \(k\)-clique-coloring of a graph \(G\) is an assignment of \(k\) colors to the vertices of \(G\) such that no clique of \(G\) is monochromatic. The smallest integer \(k\) admitting a \(k\)-clique-coloring of \(G\) is called clique-coloring number of \(G\) and denoted by \(\chi _C(G)\). In this paper, we first find a class of minimal non-clique-perfect graphs and characterize the clique-perfectness of outer-planar graphs. Secondly, we present a linear time algorithm for the optimal clique-coloring of an outer-planar graph \(G\).

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andreae T, Schughart M, Zs Tuza (1991) Clique-transversal sets of line graphs and complements of line graphs. Discret Math 88:11-20 · Zbl 0734.05077 · doi:10.1016/0012-365X(91)90055-7
[2] Bacsó G, Gravier S, Gyárfás A, Preissmann M, Sebő A (2004) Coloring the maximal cliques of graphs. SIAM J Discret Math 17:361-376 · Zbl 1056.05049 · doi:10.1137/S0895480199359995
[3] Bacsó G, Zs Tuza (2009) Clique-transversal sets and weak 2-colorings in graphs of small maximum degree. Discret Math Theor Comput Sci 11(2):15-24 · Zbl 1196.05029
[4] Balachandran V, Nagavamsi P, Rangan CP (1996) Clique transversal and clique independence on comparability graphs. Inf Process Lett 58:181-184 · doi:10.1016/0020-0190(96)00054-3
[5] Bondy JA, Murty USR (2000) Graph theory. Springer, Berlin · Zbl 1134.05001
[6] Bonomo F, Chudnovsky M, Durán G (2008) Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs. Discret Appl Math 156:1058-1082 · Zbl 1138.05030 · doi:10.1016/j.dam.2007.05.048
[7] Bonomo F, Chudnovsky M, Durán G (2009) Partial characterizations of clique-perfect graphs II: diamond-free and Helly circular-arc graphs. Discret Math 309:3485-3499 · Zbl 1227.05151 · doi:10.1016/j.disc.2007.12.054
[8] Bonomo F, Durán G, Groshaus M, Szwarcfiter JL (2006a) On clique-perfect and K-perfect graphs. Ars Comb 80:97-112 · Zbl 1224.05358
[9] Bonomo F, Durán G, Lin MC, Szwarcfiter JL (2006b) On balanced graphs. Math Program Ser B 105:233-250 · Zbl 1080.05058 · doi:10.1007/s10107-005-0651-y
[10] Bonomo F, Durán G, Safe MD, Wagler AK (2015) Clique-perfectness of complements of line graphs. Discret Appl Math 186:19-44 · Zbl 1311.05145 · doi:10.1016/j.dam.2015.01.012
[11] Bonomo F, Durán G, Soulignac F, Sueiro G (2009) Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs. Discret Appl Math 157:3511-3518 · Zbl 1213.05105 · doi:10.1016/j.dam.2009.03.017
[12] Borodin OV, Woodall DR (1995) Thirteen colouring numbers for outerplane graphs. Bull Inst Comb Appl 14:87-100 · Zbl 0836.05026
[13] Brandstädt A, Chepoi VD, Dragan FF (1997) Clique \[r\] r-domination and clique \[r\] r-packing problems on dually chordal graphs. SIAM J Discret Math 10:109-127 · Zbl 0869.05048 · doi:10.1137/S0895480194267853
[14] Campos CN, Dantas S, de Mello CP (2008) Coloring clique-hypergraphs of circulant graphs. Electron Notes Discret Math 30:189-194 · Zbl 1341.05065 · doi:10.1016/j.endm.2008.01.033
[15] Cerioli MR, Korenchendler AL (2009) Clique-coloring circular-arc graphs. Electron Notes Discret Math 35:287-292 · Zbl 1268.05067 · doi:10.1016/j.endm.2009.11.047
[16] Cerioli MR, Priscila P (2008) Clique-coloring UE and UEH graphs. Electron Notes Discret Math 30:201-206 · Zbl 1341.05067 · doi:10.1016/j.endm.2008.01.035
[17] Chang GJ, Farber M, Zs Tuza (1993) Algorithmic aspects of neighbourhood numbers. SIAM J Discret Math 6:24-29 · Zbl 0777.05085 · doi:10.1137/0406002
[18] Dahlhaus E, Manuel PD, Miller M (1998) Maximum \[h\] h-colourable subgraph problem in balanced graphs. Inf Process Lett 65:301-303 · Zbl 1338.68098 · doi:10.1016/S0020-0190(98)00019-2
[19] Défossez D (2006) Clique-coloring some classess of odd-hole-free graphs. J Graph Theory 53:233-249 · Zbl 1108.05036 · doi:10.1002/jgt.20177
[20] Défossez D (2009) Complexity of clique-coloring odd-hole-free graphs. J Graph Theory 62:139-156 · Zbl 1182.05092 · doi:10.1002/jgt.20387
[21] Duffus D, Kierstead HA, Trotter WT (1991) Fibers and ordered set coloring. J Comb Theory Ser A 58:158-164 · Zbl 0757.06001 · doi:10.1016/0097-3165(91)90083-S
[22] Durán G, Lin MC, Szwarcfiter JL (2002) On clique-transversals and clique-independent sets. Ann Oper Res 116:71-77 · Zbl 1013.90107 · doi:10.1023/A:1021363810398
[23] Even S, Tarjan RE (1975) Network flow and testing graph connectivity. SIAM J Comput 4:507-518 · Zbl 0328.90031 · doi:10.1137/0204043
[24] Guruswami V, Rangan CP (2000) Algorithmic aspects of clique-transversal and clique-independent sets. Discret Appl Math 100:183-202 · Zbl 0948.68135 · doi:10.1016/S0166-218X(99)00159-6
[25] Hoàng CT, McDiarmid C (2002) On the divisibility of graphs. Discret Math 242:145-156 · Zbl 0988.05068 · doi:10.1016/S0012-365X(01)00054-1
[26] Jenson T, Toft B (1995) Graph coloring problems. Wiley-Interscience, New York · Zbl 0855.05054
[27] Kratochvíl J, Zs Tuza (2002) On the complexity of bicoloring clique hypergraphs of graphs. J Algorithms 45:40-54 · Zbl 1030.68066 · doi:10.1016/S0196-6774(02)00221-3
[28] Lee CM, Chang MS (2006) Distance-hereditary graphs are clique-perfect. Discret Appl Math 154:525-536 · Zbl 1110.68108 · doi:10.1016/j.dam.2005.07.011
[29] Liang Z, Shan E, Kang L (2016) Clique-perfectness of claw-free planar graphs. Graphs Comb 32:2551-2562 · Zbl 1353.05091 · doi:10.1007/s00373-016-1726-7
[30] Lick DR, White A \[(1970) k\] k-degenerate graphs. Can J Math XXII: 1082-1096 · Zbl 0202.23502
[31] Lonc Z, Rival I (1987) Chains, antichains and fibres. J Comb Theory Ser A 44:207-228 · Zbl 0637.06001 · doi:10.1016/0097-3165(87)90029-X
[32] Marx D (2011) Complexity of clique coloring and related problems. Theoret Comput Sci 412:3487-3500 · Zbl 1222.05070 · doi:10.1016/j.tcs.2011.02.038
[33] Mohar B, Skrekovski R (1999) The Grötzsch theorem for the hypergraph of maximal cliques. Electron J Combin 6: #R26 · Zbl 0930.05040
[34] Shan E, Liang Z, Kang L (2014) Clique-transversal sets and clique-coloring in planar graphs. Eur J Comb 36:367-376 · Zbl 1284.05075 · doi:10.1016/j.ejc.2013.08.003
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.