3-consecutive c-colorings of graphs

Csilla Bujtás; E. Sampathkumar; Zsolt Tuza; M.S. Subramanya; Charles Dominic

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 3, page 393-405
  • ISSN: 2083-5892

Abstract

top
A 3-consecutive C-coloring of a graph G = (V,E) is a mapping φ:V → ℕ such that every path on three vertices has at most two colors. We prove general estimates on the maximum number ( χ ̅ ) 3 C C ( G ) of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with ( χ ̅ ) 3 C C ( G ) ≥ k for k = 3 and k = 4.

How to cite

top

Csilla Bujtás, et al. "3-consecutive c-colorings of graphs." Discussiones Mathematicae Graph Theory 30.3 (2010): 393-405. <http://eudml.org/doc/271061>.

@article{CsillaBujtás2010,
abstract = {A 3-consecutive C-coloring of a graph G = (V,E) is a mapping φ:V → ℕ such that every path on three vertices has at most two colors. We prove general estimates on the maximum number $(χ̅)_\{3CC\}(G)$ of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with $(χ̅)_\{3CC\}(G) ≥ k$ for k = 3 and k = 4.},
author = {Csilla Bujtás, E. Sampathkumar, Zsolt Tuza, M.S. Subramanya, Charles Dominic},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph coloring; vertex coloring; consecutive coloring; upper chromatic number},
language = {eng},
number = {3},
pages = {393-405},
title = {3-consecutive c-colorings of graphs},
url = {http://eudml.org/doc/271061},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Csilla Bujtás
AU - E. Sampathkumar
AU - Zsolt Tuza
AU - M.S. Subramanya
AU - Charles Dominic
TI - 3-consecutive c-colorings of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 3
SP - 393
EP - 405
AB - A 3-consecutive C-coloring of a graph G = (V,E) is a mapping φ:V → ℕ such that every path on three vertices has at most two colors. We prove general estimates on the maximum number $(χ̅)_{3CC}(G)$ of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with $(χ̅)_{3CC}(G) ≥ k$ for k = 3 and k = 4.
LA - eng
KW - graph coloring; vertex coloring; consecutive coloring; upper chromatic number
UR - http://eudml.org/doc/271061
ER -

References

top
  1. [1] C. Berge, Hypergraphs (North-Holland, 1989). 
  2. [2] Cs. Bujtás and Zs. Tuza, Color-bounded hypergraphs, I: General results, Discrete Math. 309 (2009) 4890-4902, doi: 10.1016/j.disc.2008.04.019. Zbl1210.05088
  3. [3] Cs. Bujtás and Zs. Tuza, Color-bounded hypergraphs, II: Interval hypergraphs and hypertrees, Discrete Math. in print, doi:10.1016/j.disc.2008.10.023 
  4. [4] G.J. Chang, M. Farber and Zs. Tuza, Algorithmic aspects of neighborhood numbers, SIAM J. Discrete Math. 6 (1993) 24-29, doi: 10.1137/0406002. Zbl0777.05085
  5. [5] S. Hedetniemi and R. Laskar, Connected domination in graphs, in: Graph Theory and Combinatorics, B. Bollobás, Ed. (Academic Press, London, 1984) 209-218. Zbl0548.05055
  6. [6] J. Lehel and Zs. Tuza, Neighborhood perfect graphs, Discrete Math. 61 (1986) 93-101, doi: 10.1016/0012-365X(86)90031-2. 
  7. [7] E. Sampathkumar, DST Project Report, No.SR/S4/MS.275/05. 
  8. [8] E. Sampathkumar, M.S. Subramanya and C. Dominic, 3-Consecutive vertex coloring of a graph, Proc. Int. Conf. ICDM (University of Mysore, India, 2008) 147-151. Zbl1231.05102
  9. [9] E. Sampathkumar and P.S. Neralagi, The neighourhood number of a graph, Indian J. Pure Appl. Math. 16 (1985) 126-132. 
  10. [10] E. Sampathkumar and H.B. Walikar, The connected domination number of a graph, J. Math. Phys. Sci. 13 (1979) 607-613. Zbl0449.05057
  11. [11] F. Sterboul, A new combinatorial parameter, in: Infinite and Finite Sets (A. Hajnal et al., Eds.), Colloq. Math. Soc. J. Bolyai, 10, Keszthely 1973 (North-Holland/American Elsevier, 1975) Vol. III pp. 1387-1404. 
  12. [12] V. Voloshin, The mixed hypergraphs, Computer Sci. J. Moldova 1 (1993) 45-52. 

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.