Planar graphs without 5-cycles or without 6-cycles. (English) Zbl 1186.05043
Let \(G\) be a graph without 5-cycles or 6-cycles. The authors show that there is either an edge \(uv\) with \(\deg(u) + \deg(v) \leq 9\), or a cycle of even length such that every other vertex is of degree 2.
The list-edge-chromatic number is the smallest \(k\) such that if each edge is assigned a set of \(k\) colors, there is always an edge-coloring using colors from each edge’s list such that adjacent edges receive distinct colors. The list-total-chromatic number is the smallest \(k\) such that if each vertex and each edge is assigned a set of \(k\) colors, there is always a coloring of the edges and vertices from each’s list such that adjacent or incident elements receive distinct colors. The linear \(k\)-arboricity of a graph is the smallest \(m\) such that the edges of \(G\) can be partitioned into \(m\) parts, each part having components that are paths of length at most \(k\).
The authors use the first result to show
The list-edge-chromatic number is the smallest \(k\) such that if each edge is assigned a set of \(k\) colors, there is always an edge-coloring using colors from each edge’s list such that adjacent edges receive distinct colors. The list-total-chromatic number is the smallest \(k\) such that if each vertex and each edge is assigned a set of \(k\) colors, there is always a coloring of the edges and vertices from each’s list such that adjacent or incident elements receive distinct colors. The linear \(k\)-arboricity of a graph is the smallest \(m\) such that the edges of \(G\) can be partitioned into \(m\) parts, each part having components that are paths of length at most \(k\).
The authors use the first result to show
- (1)
- the linear 2-arboricity of \(G\) is at most \(\lceil (\Delta(G)+1)/2\rceil + 6\),
- (2)
- the list-total-chromatic number is \(\Delta(G)+1\) if \(\Delta(G) \geq 8\), and
- (3)
- The list-edge-chromatic number is \(\Delta(G)\) if \(\Delta(G) \geq 8\).
Reviewer: Dan S. Archdeacon (Burlington)
MSC:
05C10 | Planar graphs; geometric and topological aspects of graph theory |
05C15 | Coloring of graphs and hypergraphs |
05C35 | Extremal problems in graph theory |
Keywords:
planarity; discharging; list colorings; arboricity; list edge chromatic number; list total chromatic number; linear k-arboricityReferences:
[1] | Aldred, R. E.L.; Wormald, N. C., More on the linear k-arboricity of regular graphs, Australas. J. Combin., 18, 97-104 (1998) · Zbl 0930.05075 |
[2] | Bermond, J. C.; Fouquet, J. L.; Habib, M.; Péroche, B., On linear \(k\)-arboricity, Discrete Math., 52, 123-132 (1984) · Zbl 0556.05054 |
[3] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), North-Holland: North-Holland New York · Zbl 1134.05001 |
[4] | Borodin, O. V.; Kostochka, A. V.; Woodall, D. R., List edge and list total colourings of multigraphs, J. Combin. Theory, Series B, 71, 184-204 (1997) · Zbl 0876.05032 |
[5] | Chang, G. J., Algorithmic aspects of linear \(k\)-arboricity, Taiwanese J. Math., 3, 73-81 (1999) · Zbl 0927.05073 |
[6] | Chang, G. J.; Chen, B. L.; Fu, H. L.; Huang, K. C., Linear \(k\)-arboricity on trees, Discrete Appl. Math., 103, 281-287 (2000) · Zbl 0958.05069 |
[7] | Chen, B. L.; Fu, H. L.; Huang, K. C., Decomposing graphs into forests of paths with size less than three, Australas. J. Combin., 3, 55-73 (1991) · Zbl 0758.05074 |
[8] | Fu, H. L.; Huang, K. C., The linear 2-arboricity of complete bipartite graphs, Australas. J. Combin., 38, 309-318 (1994) · Zbl 0814.05061 |
[9] | Habib, M.; Peroche, P., Some problems about linear arboricity, Discrete Math., 41, 219-220 (1982) · Zbl 0486.05053 |
[10] | Hou, J. F.; Liu, G. Z.; Cai, J. S., List edge and list total colorings of planar graphs without 4-cycles, Theoret. Comput. Sci., 369, 250-255 (2006) · Zbl 1108.05038 |
[11] | Jackson, B.; Wormald, N. C., On linear \(k\)-arboricity of cubic graphs, Discrete Math., 162, 293-297 (1996) · Zbl 0870.05036 |
[12] | Juvan, M.; Mohar, B.; Skrekovski, R., List total colourings of graphs, Combin. Probab. Comput., 7, 181-188 (1998) · Zbl 0911.05033 |
[13] | Lih, K. W.; Tong, L. D.; Wang, W. F., The linear 2-arboricity of planar graphs, Graphs and Combinatorics, 19, 241-248 (2003) · Zbl 1018.05019 |
[14] | Qian, J.; Wang, W. F., The linear 2-arboricity of planar graphs without 4-cycles, J. Zhejiang Norm. Univ., 29, 121-125 (2006) · Zbl 1107.05075 |
[15] | Thomassen, C., Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5, J. Combin. Theory, Ser. B, 75, 100-109 (1999) · Zbl 0930.05043 |
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.