Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs

• Autorzy: Ewa Kubicka , Grzegorz Kubicki , Kathleen A. McKeon
• Języki publikacji: EN

Abstrakty

EN

Given graphs G and H, a vertex coloring c : V (G) →ℕ is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ (H,G), is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G, ∑(H,G), is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for ∑(H,G), discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, Gk with the property that k more colors than χ (H,G) are required to realize ∑(H,G) for H-free colorings. More complexity results and constructions of graphs requiring extra colors are given for planar and outerplanar graphs.

Słowa kluczowe

EN

coloring; sum of colors; forbidden subgraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 3
• Strony: 541-555

Daty

wydano

2015-08-01

otrzymano

2013-02-27

poprawiono

2014-11-10

zaakceptowano

2014-11-10

online

2015-07-29

Twórcy

autor

Ewa Kubicka

• University of Louisville, USA

autor

Grzegorz Kubicki

• University of Louisville, USA University of Opole, Poland

autor

Kathleen A. McKeon

• Connecticut College, USA

Bibliografia

• [1] M. Albertson, R. Jamison, S. Hedetniemi and S. Locke, The subchromatic number of a graph, Discrete Math. 74 (1989) 33-49. doi:10.1016/0012-365X(89)90196-9[Crossref]
• [2] J. Andrews and M. Jacobson, On a generalization of chromatic number , Congr. Numer. 47 (1985) 33-48.
• [3] D. Archdeacon, A note on defective colorings of graphs in surfaces, J. Graph Theory 11 (1987) 517-519. doi:10.1002/jgt.3190110408[Crossref]
• [4] M. Borowiecki. I. Broere, M. Frick, P. Mih´ok and G. Semaniˇsin, A survey of hered- itary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50. doi:10.7151/dmgt.1037[Crossref]
• [5] I. Broere and M. Mynhardt, Generalized colorings of outer-planar and planar graphs, Graph Theory with Applications to Algorithms and Computer Science, Wiley, New York (1985) 151-161.
• [6] I. Broere, S. Dorfing and E. Jonck, Generalized chromatic numbers and hereditary properties of graphs, Discuss. Math. Graph Theory 22 (2002) 259-270. doi:10.7151/dmgt.1174[Crossref]
• [7] H. Broersma, F.V. Fomin, J. Kratochvil and G.J. Woeginger, Planar graph coloring avoiding monochromatic subgraphs: trees, and paths make it difficult, Algorithmica 44 (2006) 343-361. doi:10.1007/s00453-005-1176-8[Crossref]
• [8] M.I. Burstein, The bi-colorability of planar hypergraphs, Sakharth. SSR Mecn. Akad. Moambe 78 (1975) 293-296.
• [9] G. Chartrand, D. Geller and S. Hedetniemi, A generalization of the chromatic num- ber, Proc. Cambridge Philos. Soc. 64 (1968) 265-271. doi:10.1017/S0305004100042808[Crossref]
• [10] G. Chartrand and H. Kronk, The point-arboricity of planar graphs, J. London Math. Soc. 44 (1969) 612-616. doi:10.1112/jlms/s1-44.1.612[Crossref]
• [11] G. Chartrand, H. Kronk and C. Wall, The point-arboricity of a graph, Israel J. Math. 6 (1968) 169-175. doi:10.1007/BF02760181[Crossref]
• [12] L.J. Cowen, R.H. Cowen and D.R.Woodall, Defective colorings of graphs in surfaces; partitions into subgraphs of bounded valency, J. Graph Theory 10 (1986) 187-195. doi:10.1002/jgt.3190100207[Crossref]
• [13] L.J. Cowen, W. Goddard and C.E. Jesurum, Defective colorings revisited, J. Graph Theory 24 (1997) 205-219. doi:10.1002/(SICI)1097-0118(199703)24:3h205::AID-JGT2i3.0.CO;2-T[Crossref]
• [14] K. Dargen and K. Fraughnaugh, Conditional chromatic numbers with forbidden cycles, Linear Algebra Appl. 217 (1985) 53-66. doi:10.1016/0024-3795(94)00139-5[Crossref]
• [15] P. Erd˝os, E. Kubicka and A.J. Schwenk, Graphs that require many colors to achieve their chromatic sum, Proc. Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing 71 (1990) 17-28.
• [16] W. Goddard, Acyclic colorings of planar graphs, Discrete Math. 91 (1991) 91-94. doi:10.1016/0012-365X(91)90166-Y[Crossref]
• [17] F. Harary and K. Fraughnaugh (Jones), Conditional colorability II: bipartite varia- tions, Congr. Numer. 50 (1985) 205-218.
• [18] F. Harary and K. Fraughnaugh (Jones), Degree conditional bipartition numbers in graphs, Congr. Numer. 55 (1986) 39-50.[WoS]
• [19] E. Kubicka, The chromatic sums and efficient tree algorithms, Ph.D. Thesis,Western Michigan University (1989).
• [20] E. Kubicka, G. Kubicki and K. McKeon, Chromatic sums for colorings avoiding monochromatic subgraphs, Electron. Notes Discrete Math. 43 (2013) 247-254. doi:10.1016/j.endm.2013.07.041 [Crossref]
• [21] E. Kubicka and A. Schwenk, Introduction to chromatic sums, Congr. Numer. 71 (1990) 7-28.
• [22] K. McKeon, Generalized chromatic numbers of graphs with bipartite complements, Congr. Numer. 197 (2009) 97-105.
• [23] K. McKeon and H. Pham, Generalized chromatic numbers of graphs with prescribed complements, Congr. Numer. 191 (2008) 71-79.
• [24] K.S. Poh, On the linear vertex-arboricity of a planar graph, J. Graph Theory 14 (1990) 73-75. doi:10.1002/jgt.3190140108[Crossref]
• [25] C. Thomassen, Decomposing a planar graph into degenerate graphs, J. Combin. Theory Ser. B 65 (1995) 305-314. doi:10.1006/jctb.1995.1057 [Crossref]

Identyfikatory

DOI

10.7151/dmgt.1819