Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs

Ewa Kubicka; Grzegorz Kubicki; Kathleen A. McKeon

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 3, page 541-555
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Ewa Kubicka, Grzegorz Kubicki, and Kathleen A. McKeon. "Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs." Discussiones Mathematicae Graph Theory 35.3 (2015): 541-555. <http://eudml.org/doc/271214>.

@article{EwaKubicka2015,
abstract = {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.},
author = {Ewa Kubicka, Grzegorz Kubicki, Kathleen A. McKeon},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {coloring; sum of colors; forbidden subgraphs},
language = {eng},
number = {3},
pages = {541-555},
title = {Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs},
url = {http://eudml.org/doc/271214},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Ewa Kubicka
AU - Grzegorz Kubicki
AU - Kathleen A. McKeon
TI - Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 3
SP - 541
EP - 555
AB - 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.
LA - eng
KW - coloring; sum of colors; forbidden subgraphs
UR - http://eudml.org/doc/271214
ER -

References

top
  1. [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] Zbl0681.05033
  2. [2] J. Andrews and M. Jacobson, On a generalization of chromatic number , Congr. Numer. 47 (1985) 33-48. 
  3. [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. [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. [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. [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] Zbl1030.05038
  7. [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] Zbl1095.68075
  8. [8] M.I. Burstein, The bi-colorability of planar hypergraphs, Sakharth. SSR Mecn. Akad. Moambe 78 (1975) 293-296. 
  9. [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. [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] Zbl0175.50505
  11. [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] Zbl0164.54201
  12. [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] Zbl0596.05024
  13. [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] Zbl0877.05019
  14. [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] Zbl0824.05024
  15. [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. Zbl0704.05020
  16. [16] W. Goddard, Acyclic colorings of planar graphs, Discrete Math. 91 (1991) 91-94. doi:10.1016/0012-365X(91)90166-Y[Crossref] 
  17. [17] F. Harary and K. Fraughnaugh (Jones), Conditional colorability II: bipartite varia- tions, Congr. Numer. 50 (1985) 205-218. 
  18. [18] F. Harary and K. Fraughnaugh (Jones), Degree conditional bipartition numbers in graphs, Congr. Numer. 55 (1986) 39-50.[WoS] 
  19. [19] E. Kubicka, The chromatic sums and efficient tree algorithms, Ph.D. Thesis,Western Michigan University (1989). 
  20. [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] Zbl1317.05062
  21. [21] E. Kubicka and A. Schwenk, Introduction to chromatic sums, Congr. Numer. 71 (1990) 7-28. 
  22. [22] K. McKeon, Generalized chromatic numbers of graphs with bipartite complements, Congr. Numer. 197 (2009) 97-105. Zbl1211.05045
  23. [23] K. McKeon and H. Pham, Generalized chromatic numbers of graphs with prescribed complements, Congr. Numer. 191 (2008) 71-79. Zbl1181.05047
  24. [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] Zbl0705.05016
  25. [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] Zbl0840.05070

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.