Geodesic
On detectable colorings of graphs
Mathematica Bohemica, Tome 130 (2005) no. 4, pp. 427-445

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
Let $G$ be a connected graph of order $n \ge 3$ and let $c\: E(G) \rightarrow \lbrace 1, 2, \ldots , k\rbrace $ be a coloring of the edges of $G$ (where adjacent edges may be colored the same). For each vertex $v$ of $G$, the color code of $v$ with respect to $c$ is the $k$-tuple $c(v) = (a_1, a_2, \cdots , a_k)$, where $a_i$ is the number of edges incident with $v$ that are colored $i$ ($1 \le i \le k$). The coloring $c$ is detectable if distinct vertices have distinct color codes. The detection number $\det (G)$ of $G$ is the minimum positive integer $k$ for which $G$ has a detectable $k$-coloring. We establish a formula for the detection number of a path in terms of its order. For each integer $n \ge 3$, let $D_u(n)$ be the maximum detection number among all unicyclic graphs of order $n$ and $d_u(n)$ the minimum detection number among all unicyclic graphs of order $n$. The numbers $D_u(n)$ and $d_u(n)$ are determined for all integers $n \ge 3$. Furthermore, it is shown that for integers $k \ge 2$ and $n \ge 3$, there exists a unicyclic graph $G$ of order $n$ having $\det (G)=k$ if and only if $d_u(n) \le k \le D_u(n)$.
Let $G$ be a connected graph of order $n \ge 3$ and let $c\: E(G) \rightarrow \lbrace 1, 2, \ldots , k\rbrace $ be a coloring of the edges of $G$ (where adjacent edges may be colored the same). For each vertex $v$ of $G$, the color code of $v$ with respect to $c$ is the $k$-tuple $c(v) = (a_1, a_2, \cdots , a_k)$, where $a_i$ is the number of edges incident with $v$ that are colored $i$ ($1 \le i \le k$). The coloring $c$ is detectable if distinct vertices have distinct color codes. The detection number $\det (G)$ of $G$ is the minimum positive integer $k$ for which $G$ has a detectable $k$-coloring. We establish a formula for the detection number of a path in terms of its order. For each integer $n \ge 3$, let $D_u(n)$ be the maximum detection number among all unicyclic graphs of order $n$ and $d_u(n)$ the minimum detection number among all unicyclic graphs of order $n$. The numbers $D_u(n)$ and $d_u(n)$ are determined for all integers $n \ge 3$. Furthermore, it is shown that for integers $k \ge 2$ and $n \ge 3$, there exists a unicyclic graph $G$ of order $n$ having $\det (G)=k$ if and only if $d_u(n) \le k \le D_u(n)$.
DOI : 10.21136/MB.2005.134214
Classification : 05C15, 05C70
Keywords: detectable coloring; detection number; unicyclic graph 
Escuadro, Henry; Zhang, Ping. On detectable colorings of graphs. Mathematica Bohemica, Tome 130 (2005) no. 4, pp. 427-445. doi: 10.21136/MB.2005.134214
@article{10_21136_MB_2005_134214,
     author = {Escuadro, Henry and Zhang, Ping},
     title = {On detectable colorings of graphs},
     journal = {Mathematica Bohemica},
     pages = {427--445},
     year = {2005},
     volume = {130},
     number = {4},
     doi = {10.21136/MB.2005.134214},
     mrnumber = {2182387},
     zbl = {1111.05034},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2005.134214/}
}
TY  - JOUR
AU  - Escuadro, Henry
AU  - Zhang, Ping
TI  - On detectable colorings of graphs
JO  - Mathematica Bohemica
PY  - 2005
SP  - 427
EP  - 445
VL  - 130
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2005.134214/
DO  - 10.21136/MB.2005.134214
LA  - en
ID  - 10_21136_MB_2005_134214
ER  - 
%0 Journal Article
%A Escuadro, Henry
%A Zhang, Ping
%T On detectable colorings of graphs
%J Mathematica Bohemica
%D 2005
%P 427-445
%V 130
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2005.134214/
%R 10.21136/MB.2005.134214
%G en
%F 10_21136_MB_2005_134214

[1] M. Aigner, E. Triesch: Irregular assignments and two problems á la Ringel. Topics in Combinatorics and Graph Theory. (R. Bodendiek and R. Henn, eds.). Physica, Heidelberg (1990), 29–36. | MR

[2] M. Aigner, E. Triesch, Z. Tuza: Irregular assignments and vertex-distinguishing edge-colorings of graphs. Combinatorics ’90, Proc. Conf., Gaeta/Italy 1990, Elsevier Science Pub., New York (1992), 1–9. | MR

[3] A. C. Burris: On graphs with irregular coloring number $2$. Congr. Numerantium 100 (1994), 129–140. | MR | Zbl

[4] A. C. Burris: The irregular coloring number of a tree. Discrete Math. 141 (1995), 279–283. | DOI | MR | Zbl

[5] G. Chartrand, H. Escuadro, F. Okamoto, P. Zhang: Detectable colorings of graphs. (to appear). | MR

[6] G. Chartrand, P. Zhang: Introduction to Graph Theory. McGraw-Hill, Boston, 2005.

Cité par Sources :