Edge coloring of planar graphs which any two short cycles are adjacent at most once. (English) Zbl 1278.05084
Summary: By applying discharging methods and properties of critical graphs, we prove that every simple planar graph \(G\) is of class 1 if \(\Delta(G)=6\) and any \(k\)-cycle is adjacent to at most one \(k\)-cycle for some \(k\) (\(k=3,4,5\)).
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C15 | Coloring of graphs and hypergraphs |
References:
| [1] | Fiorini, S.; Wilson, R. J., Edge-Colourings of Graphs (1977), Pitman: Pitman London · Zbl 0421.05023 |
| [2] | Vizing, V. G., Critical graphs with given chromatic class, Diskretn. Anal., 5, 1, 9-17 (1965) · Zbl 0171.44902 |
| [3] | Sanders, D. P.; Zhao, Y., Planar graphs of maximum degree seven are class 1, J. Comb. Theory, Ser. B, 8, 2, 201-212 (2001) · Zbl 1024.05031 |
| [4] | Zhang, L., Every planar with maximum degree 7 is of class 1, Graphs Comb., 16, 4, 467-495 (2000) · Zbl 0988.05042 |
| [5] | Li, X.; Luo, R., Edge coloring of embedded graphs with large girth, Graphs Comb., 19, 3, 393-401 (2003) · Zbl 1023.05050 |
| [6] | Zhou, G., A note on graphs of class 1, Discrete Math., 262, 1-3, 339-345 (2003) · Zbl 1014.05028 |
| [7] | Bu, Y.; Wang, W., Some sufficient conditions for a planar graph of maximum degree six to be class 1, Discrete Math., 306, 13, 1440-1445 (2006) · Zbl 1095.05014 |
| [8] | Wang, W.; Chen, Y., A sufficient condition for a planar graph to be class 1, Theor. Comput. Sci., 385, 1-3, 71-77 (2007) · Zbl 1125.68090 |
| [9] | Ni, W., Edge colorings of planar graphs for maximum degree six without adjacent k-cycles, J. East China Norm. Univ. Nat. Sci., 153, 20-26 (2010) |
| [10] | Ni, W., Edge colorings of planar graphs with \(\Delta = 6\) without short cycles contain chords, J. Nanjing Norm. Univ. Nat. Sci., 34, 3, 19-24 (2011) |
| [11] | Chen, Y.; Wang, W., A sufficient condition for a planar graph to be of class 1, J. Zhejiang Norm. Univ. Nat. Sci., 30, 4, 416-420 (2007) · Zbl 1174.05453 |
| [12] | W, Y., Some Results on Edge Partitions of Planar Graphs (2007), School of Mathematics and System Science, Shandong University |
| [13] | Ni, W., Edge colorings of planar graphs with maximum degree five, J. East China Norm. Univ. Nat. Sci., 156, 2, 32-38 (2011) |
| [14] | Ni, W., Edge colorings of planar graphs without adjacent special cycles, Ars Comb., 105, 7, 247-256 (2012) · Zbl 1274.05170 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
