پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 43 |
| تعداد شمارهها | 1,639 |
| تعداد مقالات | 13,334 |
| تعداد مشاهده مقاله | 29,915,294 |
| تعداد دریافت فایل اصل مقاله | 11,969,010 |
Edge-group choosability of outerplanar and near-outerplanar graphs | ||
| Transactions on Combinatorics | ||
| دوره 9، شماره 4، اسفند 2020، صفحه 211-216 اصل مقاله (227.66 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2020.116355.1633 | ||
| نویسنده | ||
| Amir Khamseh* | ||
| Department of Mathematics, Kharazmi University, 15719-14911, Tehran, Iran | ||
| چکیده | ||
| Let $\chi_{gl}(G)$ be the {\it{group choice number}} of $G$. A graph $G$ is called {\it{edge-$k$-group choosable}} if its line graph is $k$-group choosable. The {\it{group-choice index}} of $G$, $\chi'_{gl}(G)$, is the smallest $k$ such that $G$ is edge-$k$-group choosable, that is, $\chi'_{gl}(G)$ is the group chice number of the line graph of $G$, $\chi_{gl}(\ell(G))$. It is proved that, if $G$ is an outerplanar graph with maximum degree $D<5$, or if $G$ is a $({K_2}^c+(K_1 \cup K_2))$-minor-free graph, then $\chi'_{gl}(G)\leq D(G)+1$. As a straightforward consequence, every $K_{2,3}$-minor-free graph $G$ or every $K_4$-minor-free graph $G$ is edge-$(D(G)+1)$-group choosable. Moreover, it is proved that if $G$ is an outerplanar graph with maximum degree $D\geq 5$, then $\chi'_{gl}(G)\leq D$. | ||
| کلیدواژهها | ||
| List coloring؛ Group choosability؛ Edge-group choosability | ||
| مراجع | ||
|
[1] B. Bollobás, A. J. Harris, List-colorings of graphs, Graphs Combin., 1 (1985) 115–127.
[2] O. V. Borodin, A. V. Kostochka and D. R. Woodall, List edge and list total colourings of multigraphs, J. Combin. Theory Ser. B, 71 (1997) 184–204. [3] O. V. Borodin and D. R. Woodall , Thirteen colouring numbers for outerplane graphs, Bul. Inst. Combin. and Appl., 14 (1995) 87–100. [4] H. Chuang, H. J. Lai, G. R. Omidi, K. Wang and N. Zakeri, On group choosability of graphs II, Graphs Combin., 30 (2014) 549–563. [5] H. Chuang, H. J. Lai, G. R. Omidi and N. Zakeri, On group choosability of graphs I, Ars. Combin., 126 (2016) 195–209. [6] R. Diestel, Graph Theory (3rd edition), Springer, Berlin, 2005.
[7] J. Duffin, Topology of series-parallel networks, J. Math. Anal. Appl., 10 (1965) 303–318.
[8] P. Erdős, A. L. Robin and H. Taylor, Choosability in graphs, Congr. Numer., 26 (1979) 125–157.
[9] F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B, 63 (1995) 153–158.
[10] R. Häggkvist and J. Janssen, New bounds on the list-chromatic index of the complete graph and other simple graphs, Combin. Probab. Comput., 6 (1997) 295–313. [11] T. J. Hetherington and D. R. Woodall, Edge and total choosability of near-outerplanar graphs, Electron. J. Combin., 13 (2006) Research Paper 98, 7 pp. [12] F. Jaeger, N. Linial, C. Payan and M. Tarsi, Group connectivity of graphs-a non-homogeneouse analogue of nowhere- zero flow properties, J. Combin. Theory Ser. B, 56 (1992) 165–182. [13] A. V. Kostochka, List edge chromatic number of graphs with large girth, Discrete Math., 101 (1992) 189–201.
[14] D. Král and P. Nejedlý, Group coloring and list group coloring are ΠP2 -Complete, Mathematical foundations of computer science, Lecture Notes in Comput. Sci., 3153, Springer, Berlin, (2004) 274–286. [15] G. R. Omidi, A note on group choosability of graphs with girth at least 4, Graphs Combin., 27 (2011) 269–273.
[16] D. R. Woodall, A short proof of a theorem of Dirac’s about Hadwiger’s conjecture, J. Graph Theory, 16 (1992) 79–80. [17] V. G. Vizing, Coloring the vertices of a graph in prescribed colors (in Russian), Methody Diskret. Analiz, 29 (1976)¯ 3–10. [18] W. F. Wang and K. W. Lih, Choosability, edge-choosability and total choosability of outerplane graphs, European J. Combin., 22 (2001) 71–78. [19] D. R. Woodall, Edge-choosability of multicircuits, Discrete Math., 202 (1999) 271–277. | ||
|
آمار تعداد مشاهده مقاله: 254 تعداد دریافت فایل اصل مقاله: 279 |
||