More Web Proxy on the site http://driver.im/

article

Improper colorability of planar graphs without prescribed short cycles

Authors:

Jinghan XuAuthors Info & Claims

Discrete Mathematics, Volume 322

Pages 5 - 14

https://doi.org/10.1016/j.disc.2013.12.023

Published: 01 May 2014 Publication History

Abstract

Let d"1,d"2,...,d"k be k non-negative integers. A graph G is (d"1,d"2,...,d"k)-colorable, if the vertex set of G can be partitioned into subsets V"1,V"2,...,V"k such that the subgraph G[V"i] induced by V"i has maximum degree at most d"i for i=1,2,...,k. It is known that planar graphs without cycles of length 4 or l for any l@?{5,6} are (1,1,0)-colorable. In this paper, we prove that planar graphs without cycles of length 4 or l for any l@?{7,8} are also (1,1,0)-colorable. Some conjectures and problems for further study are presented.

References

[1]

Appel, K. and Haken, W., Every planar map is four colorable, part I. Discharging. Illinois J. Math. v21. 429-490.

[2]

Appel, K. and Haken, W., Every planar map is four colorable. part II. Reducibility. Illinois J. Math. v21. 491-567.

[3]

G.J. Chang, F. Havet, M. Montassier, A. Raspaud, Steinberg's Conjecture and nearing-colorings, Preprint.

[4]

Cowen, L.J., Cowen, R.H. and Woodall, D.R., Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency. J. Graph Theory. v10 i2. 187-195.

[5]

Dong, W. and Xu, B., A note on list improper coloring of plane graphs. Discrete Appl. Math. v157. 433-436.

Digital Library

[6]

Eaton, N. and Hull, T., Defective list colorings of planar graphs. Bull. Inst. Combin. Appl. v25. 79-87.

[7]

Ein dreifarbensatz für dreikreisfreie netze auf der kugel. Math-Natur. Reih. v8. 109-120.

[8]

Hill, O., Smith, D., Wang, Y., Xu, L. and Yu, G., Planar graphs without 4-cycles or 5-cycles are (3,0,0)-colorable. Discrete Math. v313. 2312-2317.

[9]

Hill, O. and Yu, G., A relaxation of Steinberg's conjecture. SIAM J. Discrete Math. v27 i1. 584-596.

[10]

Lih, K., Song, Z., Wang, W. and Zhang, K., A note on list improper coloring planar graphs. Appl. Math. Lett. v14. 269-273.

[11]

Škrekovski, R., List improper coloring of planar graphs. Combin. Probab. Comput. v8. 293-299.

Digital Library

[12]

Steinberg, R., The state of the three color problem, Quo Vadis, graph theory. Ann. Discrete Math. v55. 211-248.

[13]

Wang, Y. and Xu, L., Improper choosabolity of planar graphs without 4-cycles. SIAM J. Discrete Math. v27 i4. 2029-2037.

[14]

Xu, B., On (3;1)¿-coloring of plane graphs. SIAM J. Discrete Math. v23 i1. 205-220.

[15]

Xu, L., Miao, Z. and Wang, Y., Every planar graph with cycles of length neither 4 nor 5 is (1,1,0)-colorable. J. Comb. Optim.

[16]

Xu, L. and Wang, Y., Improper colorability of planar graphs with cycles of length neighbor 4 nor 6. Sci. Sin. Math. v43. 15-24.

Cited By

Zhang MChen MWang Y(2017)A sufficient condition for planar graphs with girth 5 to be (1, 7)-colorableJournal of Combinatorial Optimization10.1007/s10878-016-0010-333:3(847-865)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s10878-016-0010-3
Zhang CWang YChen M(2016)Planar graphs without adjacent cycles of length at most five are (1,1,0) -colorableDiscrete Mathematics10.1016/j.disc.2016.06.011339:12(3032-3042)Online publication date: 6-Dec-2016
https://dl.acm.org/doi/10.1016/j.disc.2016.06.011
Chen MWang YLiu PXu J(2016)Planar graphs without cycles of length 4 or 5 are ( 2 , 0 , 0 ) -colorableDiscrete Mathematics10.1016/j.disc.2015.10.029339:2(886-905)Online publication date: 6-Feb-2016
https://dl.acm.org/doi/10.1016/j.disc.2015.10.029
Show More Cited By

Improper colorability of planar graphs without prescribed short cycles
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
    2. Graph theory
2. Theory of computation

Recommendations

Equitable colorings of planar graphs without short cycles

An equitable coloring of a graph is a proper vertex coloring such that the sizes of every two color classes differ by at most 1. Chen, Lih, and Wu conjectured that every connected graph G with maximum degree @D>=2 has an equitable coloring with @D ...
The (3,3)-colorability of planar graphs without 4-cycles and 5-cycles
Abstract
A graph G is called (d 1 , … , d r)-colorable if its vertex set can be partitioned into r sets V 1 , … , V r such that the maximum degree of the induced subgraph G [ V i ] of G is at most d i for i ∈ { 1 , … , r }. Steinberg ...
$$(1,0,0)$$(1,0,0)-Colorability of planar graphs without prescribed short cycles

Let $$d_1, d_2,\ldots ,d_k$$d1,d2, ,dk be $$k$$k non-negative integers. A graph $$G$$G is $$(d_1,d_2,\ldots ,d_k)$$(d1,d2, ,dk)-colorable, if the vertex set of $$G$$G can be partitioned into subsets $$V_1,V_2,\ldots ,V_k$$V1,V2, ,Vk such that the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Mathematics

Discrete Mathematics Volume 322, Issue

May, 2014

77 pages

ISSN:0012-365X

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2014.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 May 2014

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang MChen MWang Y(2017)A sufficient condition for planar graphs with girth 5 to be (1, 7)-colorableJournal of Combinatorial Optimization10.1007/s10878-016-0010-333:3(847-865)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s10878-016-0010-3
Zhang CWang YChen M(2016)Planar graphs without adjacent cycles of length at most five are (1,1,0) -colorableDiscrete Mathematics10.1016/j.disc.2016.06.011339:12(3032-3042)Online publication date: 6-Dec-2016
https://dl.acm.org/doi/10.1016/j.disc.2016.06.011
Chen MWang YLiu PXu J(2016)Planar graphs without cycles of length 4 or 5 are ( 2 , 0 , 0 ) -colorableDiscrete Mathematics10.1016/j.disc.2015.10.029339:2(886-905)Online publication date: 6-Feb-2016
https://dl.acm.org/doi/10.1016/j.disc.2015.10.029
Wang YXu J(2015)Decomposing a planar graph without cycles of length 5 into a matching and a 3-colorable graphEuropean Journal of Combinatorics10.1016/j.ejc.2014.08.02043:C(98-123)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.ejc.2014.08.020

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents