# Defective choosability of graphs in surfaces

Discussiones Mathematicae Graph Theory (2011)

- Volume: 31, Issue: 3, page 441-459
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topDouglas R. Woodall. "Defective choosability of graphs in surfaces." Discussiones Mathematicae Graph Theory 31.3 (2011): 441-459. <http://eudml.org/doc/270878>.

@article{DouglasR2011,

abstract = {It is known that if G is a graph that can be drawn without edges crossing in a surface with Euler characteristic ε, and k and d are positive integers such that k ≥ 3 and d is sufficiently large in terms of k and ε, then G is (k,d)*-colorable; that is, the vertices of G can be colored with k colors so that each vertex has at most d neighbors with the same color as itself. In this paper, the known lower bound on d that suffices for this is reduced, and an analogous result is proved for list colorings (choosability). Also, the recent result of Cushing and Kierstead, that every planar graph is (4,1)*-choosable, is extended to $K_\{3,3\}$-minor-free and K₅-minor-free graphs.},

author = {Douglas R. Woodall},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {list coloring; defective coloring; minor-free graph},

language = {eng},

number = {3},

pages = {441-459},

title = {Defective choosability of graphs in surfaces},

url = {http://eudml.org/doc/270878},

volume = {31},

year = {2011},

}

TY - JOUR

AU - Douglas R. Woodall

TI - Defective choosability of graphs in surfaces

JO - Discussiones Mathematicae Graph Theory

PY - 2011

VL - 31

IS - 3

SP - 441

EP - 459

AB - It is known that if G is a graph that can be drawn without edges crossing in a surface with Euler characteristic ε, and k and d are positive integers such that k ≥ 3 and d is sufficiently large in terms of k and ε, then G is (k,d)*-colorable; that is, the vertices of G can be colored with k colors so that each vertex has at most d neighbors with the same color as itself. In this paper, the known lower bound on d that suffices for this is reduced, and an analogous result is proved for list colorings (choosability). Also, the recent result of Cushing and Kierstead, that every planar graph is (4,1)*-choosable, is extended to $K_{3,3}$-minor-free and K₅-minor-free graphs.

LA - eng

KW - list coloring; defective coloring; minor-free graph

UR - http://eudml.org/doc/270878

ER -

## References

top- [1] D. Archdeacon, A note on defective colorings of graphs in surfaces, J. Graph Theory 11 (1987) 517-519, doi: 10.1002/jgt.3190110408. Zbl0654.05030
- [2] L.J. Cowen, R.H. Cowen and D.R. Woodall, Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency, J. Graph Theory 10 (1986) 187-195, doi: 10.1002/jgt.3190100207. Zbl0596.05024
- [3] L. Cowen, W. Goddard and C.E. Jesurum, Defective coloring revisited, J. Graph Theory 24 (1997) 205-219, doi: 10.1002/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T Zbl0877.05019
- [4] W. Cushing and H.A. Kierstead, Planar graphs are 1-relaxed, 4-choosable, European J. Combin. 31 (2010) 1385-1397, doi: 10.1016/j.ejc.2009.11.013. Zbl1221.05077
- [5] G.A. Dirac, A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc. 27 (1952) 85-92, doi: 10.1112/jlms/s1-27.1.85. Zbl0046.41001
- [6] N. Eaton and T. Hull, Defective list colorings of planar graphs, Bull Inst. Combin. Appl. 25 (1999) 79-87. Zbl0916.05026
- [7] S. Gutner, The complexity of planar graph choosability, Discrete Math. 159 (1996) 119-130, doi: 10.1016/0012-365X(95)00104-5. Zbl0865.05066
- [8] W. He, W. Miao and Y. Shen, Another proof of the 5-choosability of K₅-minor-free graphs, Discrete Math. 308 (2008) 4024-4026, doi: 10.1016/j.disc.2007.07.089. Zbl1155.05023
- [9] M. Mirzakhani, A small non-4-choosable planar graph, Bull Inst. Combin. Appl. 17 (1996) 15-18. Zbl0860.05029
- [10] N. Robertson, P.D. Seymour and R. Thomas, Hadwiger's conjecture for K₆-free graphs, Combinatorica 13 (1993) 279-361, doi: 10.1007/BF01202354. Zbl0830.05028
- [11] R. Skrekovski, Choosability of K₅-minor-free graphs, Discrete Math. 190 (1998) 223-226, doi: 10.1016/S0012-365X(98)00158-7. Zbl0955.05043
- [12] R. Skrekovski, List improper colourings of planar graphs, Combin. Probab. Comput. 8 (1999) 293-299, doi: 10.1017/S0963548399003752. Zbl0940.05031
- [13] C. Thomassen, Every planar graph is 5-choosable, J. Combin. Theory (B) 62 (1994) 180-181, doi: 10.1006/jctb.1994.1062. Zbl0805.05023
- [14] M. Voigt, List colourings of planar graphs, Discrete Math. 120 (1993) 215-219, doi: 10.1016/0012-365X(93)90579-I. Zbl0790.05030
- [15] K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937) 570-590, doi: 10.1007/BF01594196. Zbl63.0550.01
- [16] D.R. Woodall, Improper colourings of graphs, in: R. Nelson and R.J. Wilson (eds.), Graph Colourings, Pitman Research Notes in Math. 218 (Longman, Harlow, Essex, 1990) 45-63. Zbl0693.05028
- [17] D.R. Woodall, List Colourings of Graphs, in: J.W.P. Hirschfeld (ed), Surveys in Combinatorics, 2001, London Math. Soc. Lecture Note Series 288 (Cambridge University Press, 2001) 269-301.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.