# 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

## Access Full Article

top## Abstract

top## How to cite

topCsilla 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] C. Berge, Hypergraphs (North-Holland, 1989).
- [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] 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] 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] 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] J. Lehel and Zs. Tuza, Neighborhood perfect graphs, Discrete Math. 61 (1986) 93-101, doi: 10.1016/0012-365X(86)90031-2.
- [7] E. Sampathkumar, DST Project Report, No.SR/S4/MS.275/05.
- [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] E. Sampathkumar and P.S. Neralagi, The neighourhood number of a graph, Indian J. Pure Appl. Math. 16 (1985) 126-132.
- [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] 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] V. Voloshin, The mixed hypergraphs, Computer Sci. J. Moldova 1 (1993) 45-52.

## Citations in EuDML Documents

top## NotesEmbed ?

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