Geodesic
3-consecutive c-colorings of graphs
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 3, pp. 393-405.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: graph coloring, vertex coloring, consecutive coloring, upper chromatic number 
@article{DMGT_2010_30_3_a3,
     author = {Bujt\'as, Csilla and Sampathkumar, E. and Tuza, Zsolt and Subramanya, M. and Dominic, Charles},
     title = {3-consecutive c-colorings of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {393--405},
     publisher = {mathdoc},
     volume = {30},
     number = {3},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a3/}
}
TY  - JOUR
AU  - Bujtás, Csilla
AU  - Sampathkumar, E.
AU  - Tuza, Zsolt
AU  - Subramanya, M.
AU  - Dominic, Charles
TI  - 3-consecutive c-colorings of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 393
EP  - 405
VL  - 30
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a3/
LA  - en
ID  - DMGT_2010_30_3_a3
ER  - 
%0 Journal Article
%A Bujtás, Csilla
%A Sampathkumar, E.
%A Tuza, Zsolt
%A Subramanya, M.
%A Dominic, Charles
%T 3-consecutive c-colorings of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 393-405
%V 30
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a3/
%G en
%F DMGT_2010_30_3_a3
Bujtás, Csilla; Sampathkumar, E.; Tuza, Zsolt; Subramanya, M.; Dominic, Charles. 3-consecutive c-colorings of graphs. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 3, pp. 393-405. http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a3/

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

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

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

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

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

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