Defective choosability of graphs in surfaces

Douglas R. Woodall

Discussiones Mathematicae Graph Theory (2011)

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

Abstract

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

How to cite

top

Douglas 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. [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. [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. [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. [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. [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. [6] N. Eaton and T. Hull, Defective list colorings of planar graphs, Bull Inst. Combin. Appl. 25 (1999) 79-87. Zbl0916.05026
  7. [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. [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. [9] M. Mirzakhani, A small non-4-choosable planar graph, Bull Inst. Combin. Appl. 17 (1996) 15-18. Zbl0860.05029
  10. [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. [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. [12] R. Skrekovski, List improper colourings of planar graphs, Combin. Probab. Comput. 8 (1999) 293-299, doi: 10.1017/S0963548399003752. Zbl0940.05031
  13. [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. [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. [15] K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937) 570-590, doi: 10.1007/BF01594196. Zbl63.0550.01
  16. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.