Geodesic
Vertex colorings of graph with the majority restrictions on the consuming colors
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 4, pp. 21-30 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Vertex colorings of a graph under the condition that every vertex has the maximal feasible color are considered. The chromatical criterion for such prescription which generalizes the Vitaver theorem is given. We estimate the maximal value of the prescribed color needed for a prescription to be chromatical. The analogies of the Nordhause–Gaddum theorem on interdependence of chromatic characteristics of the graph and the complementary graph are obtained. Bibl. 7.
Keywords: majority prescription, feasible coloring, chromat of graph. 
@article{DA_2009_16_4_a1,
     author = {V. G. Vizing},
     title = {Vertex colorings of graph with the majority restrictions on the consuming colors},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {21--30},
     year = {2009},
     volume = {16},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_4_a1/}
}
TY  - JOUR
AU  - V. G. Vizing
TI  - Vertex colorings of graph with the majority restrictions on the consuming colors
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 21
EP  - 30
VL  - 16
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_4_a1/
LA  - ru
ID  - DA_2009_16_4_a1
ER  - 
%0 Journal Article
%A V. G. Vizing
%T Vertex colorings of graph with the majority restrictions on the consuming colors
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 21-30
%V 16
%N 4
%U http://geodesic.mathdoc.fr/item/DA_2009_16_4_a1/
%G ru
%F DA_2009_16_4_a1
V. G. Vizing. Vertex colorings of graph with the majority restrictions on the consuming colors. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 4, pp. 21-30. http://geodesic.mathdoc.fr/item/DA_2009_16_4_a1/

[1] Vizing V. G., “Kriticheskie grafy s dannym khromaticheskim klassom”, Diskret. analiz, 5, In-t matematiki SO AN SSSR, Novosibirsk, 1965, 9–17 | MR

[2] Vizing V. G., “Raskraska vershin grafa v predpisannye tsveta”, Metody diskret. analiza v teorii kodov i skhem, 29, In-t matematiki SO AN SSSR, Novosibirsk, 1976, 3–10 | MR

[3] Vitaver L. M., “Nakhozhdenie minimalnykh raskrasok vershin grafa s pomoschyu bulevykh stepenei matritsy smezhnosti”, Dokl. AN SSSR, 147:4 (1962), 758–759 | MR | Zbl

[4] Erdős P., Rubin A. L., Taylor H., “Choosability in graphs”, Congr. Num., 26 (1980), 125–157 | MR

[5] Jensen T. R., Toft B., Graph coloring problems, John Wiley Sons, New York, 1995, 296 p. | MR | Zbl

[6] Nordhaus E. A., Gaddum J. W., “On complementary graphs”, Amer. Math. Monthly, 63 (1966), 175–177 | DOI | MR

[7] Szekeres G., Wilf H. S., “An inequality for the chromatic number of a graph”, J. Combin. Theory, 4 (1968), 1–3 | DOI | MR