Colour-blind can distinguish colour pallets

被引:0
作者
Przybylo, Jakub [1 ]
机构
[1] AGH Univ Sci & Technol, PL-30059 Krakow, Poland
关键词
Neighbour distinguishing colouring; Colour pallet; Colour-blind;
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let c: E -> {1,...,k}be an edge colouring of a connected graph G=(V,E). Each vertex v is endowed with a naturally defined pallet under c,understood as the multiset of colours incident with v. If delta(G)>= 2,we obviously (for k large enough) may colour the edges of G so that adjacent vertices are distinguished by their pallets of colours.Suppose then that our coloured graph is examined by a person who is unable to name colours, but perceives if two object placed next to each other are coloured differently. Can we colour G so that this individual can distinguish colour pallets of adjacent vertices? It is proved that if delta(G) is large enough, then it is possible using just colours 1, 2 and 3.This result is sharp and improves all earlier ones.It also constitutes a strengthening of a result by Addario-Berry, Aldred, Dalal and Reed (2005).
引用
收藏
页数:6
相关论文
共 7 条
[1]   Degree constrained subgraphs [J].
Addario-Berry, L. ;
Dalal, K. ;
Reed, B. A. .
DISCRETE APPLIED MATHEMATICS, 2008, 156 (07) :1168-1174
[2]   Vertex colouring edge partitions [J].
Addario-Berry, L ;
Aldred, REL ;
Dalal, K ;
Reed, BA .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 94 (02) :237-244
[3]   Vertex-colouring edge-weightings [J].
Addario-Berry, Louigi ;
Dalal, Ketan ;
McDiarmid, Colin ;
Reed, Bruce A. ;
Thomason, Andrew .
COMBINATORICA, 2007, 27 (01) :1-12
[4]  
Kalinowski R, 2013, ELECTRON J COMB, V20
[5]   Vertex-coloring edge-weightings: Towards the 1-2-3-conjecture [J].
Kalkowski, Maciej ;
Karonski, Michal ;
Pfender, Florian .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2010, 100 (03) :347-349
[6]   Edge weights and vertex colours [J].
Karonski, M ;
Luczak, T ;
Thomason, A .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2004, 91 (01) :151-157