Edge-group choosability of outerplanar and near-outerplanar graphs

Document Type : Research Paper

Author

Department of Mathematics, Kharazmi University, 15719-14911, Tehran, Iran

Abstract

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

Keywords

Main Subjects

References

[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.
Transactions on Combinatorics
Volume 9, Issue 4 - Serial Number 4
December 2020
Pages 211-216

Files

Cited by

History

  • Receive Date: 09 April 2019
  • Revise Date: 15 July 2020
  • Accept Date: 20 July 2020
  • Published Online: 01 December 2020

Share

How to cite

Statistics