Improper coloring of sparse graphs with a given girth, I: (0,1) -colorings of triangle-free graphs
Kim, J.; Kostochka, A.; Zhu, X.
European Journal of Combinatorics 42: 26-48
2014
ISSN/ISBN: 0195-6698 DOI: 10.1016/j.ejc.2014.05.003
Accession: 084686343
Full-Text Article emailed within 0-6 h
Payments are secure & encrypted
References
Kim, J.; Kostochka, A.; Zhu, X. 2015: Improper Coloring of Sparse Graphs with a Given Girth, II: Constructions Journal of Graph Theory 81(4): 403-413Škrekovski, R. 2000: List improper colorings of planar graphs with prescribed girth Discrete Mathematics 214(1-3): 221-233
Ochem, P.; Pinlou, A. 2013: Oriented Coloring of Triangle-Free Planar Graphs and 2-Outerplanar Graphs Graphs and Combinatorics 30(2): 439-453
Dvorak, Z.; Kral', D.; Thomas, R. 2021: Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs Journal of Combinatorial Theory. Series B 150: 270-304
Kim, J.; Ok, S. 2017: Dynamic choosability of triangle-free graphs and sparse random graphs Journal of Graph Theory 87(3): 347-355
Charpentier, C. 2017: The coloring game on planar graphs with large girth, by a result on sparse cactuses Discrete Mathematics 340(5): 1069-1073
Benevides, F.S.; Hoppen, C.; Sampaio, R.M. 2017: Edge-colorings of graphs avoiding complete graphs with a prescribed coloring Discrete Mathematics 340(9): 2143-2160
Dvok, Z.; Postle, L. 2022: Triangle-free planar graphs with at most 64n 3-colorings Journal of Combinatorial Theory. Series B 156: 294-298
Asadi, A.; Dvorak, Z.; Postle, L.; Thomas, R. 2013: Sub-exponentially many 3-colorings of triangle-free planar graphs Journal of Combinatorial Theory. Series B 103(6): 706-712
Ochem, P. 2004: Oriented colorings of triangle-free planar graphs Information Processing Letters 92(2): 71-76
Kelly, T.; Postle, L. 2017: Exponentially many 4-list-colorings of triangle-free graphs on surfaces Journal of Graph Theory 87(2): 230-238
Simanihuruk, M. 2015: On defective colorings of triangle-free graphs with prescribed maximum degree Far East Journal of Mathematical Sciences 96(3): 285-301
Wang, J.H.; Ma, Q.L.; Han, X. 2015: Neighbor sum distinguishing total colorings of triangle free planar graphs Acta Mathematica Sinica, English Series 31(2): 216-224
Thomassen, C. 2023: Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles Journal of Combinatorial Theory. Series B 158: 301-312
Hage, J.; Harju, T.; Welzl, E. 2002: Euler graphs, triangle-free graphs and bipartite graphs in switching classes Lecture Notes in Computer Science 2505: 148-160
Dvořák, Z.; Lidický, B. 2017: Fine Structure of 4-Critical Triangle-Free Graphs II. Planar Triangle-Free Graphs with two Precolored 4-Cycles SIAM Journal on Discrete Mathematics 31(2): 865-874
Kral, D.; Stehlik, M. 2009: Coloring of Triangle-Free Graphs on the Double Torus Siam Journal on Discrete Mathematics 22(2): 541-553
Gimbel, J.; Thomassen, C. 2000: Coloring triangle-free graphs with fixed size Discrete Mathematics 219(1-3): 275-277
Dutton, R.D. 2019: Coloring and Domination of Vertices in Triangle-free Graphs Journal of Combinatorial Mathematics and Combinatorial Computing 111: 137-143
Bu, Y.; Zhang, S. 2017: Backbone coloring for triangle-free planar graphs Acta Mathematicae Applicatae Sinica, English Series 33(3): 819-824