×

Lower bounds on the number of edges in edge-chromatic-critical graphs with fixed maximum degrees. (English) Zbl 1298.05126

Summary: In this article, we provide new lower bounds for the size of edge chromatic critical graphs with maximum degrees of 10, 11, 12, 13, 14, furthermore we characterize their class one properties.

MSC:

05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beineke, L. W.; Fiorini, S., On small graphs critical with respect to edge-colourings, Discrete Math., 16, 109-121 (1976) · Zbl 0344.05121
[2] Bokal, D.; Brinkmann, G.; Grünewald, S., Chromatic-index-critical graphs of orders 13 and 14, Discrete Math., 300, 16-29 (2005) · Zbl 1073.05024
[3] Brinkmann, G.; Steffen, E., 3- and 4-critical graphs of small even order, Discrete Math., 169, 193-197 (1997) · Zbl 0948.05032
[4] Brinkmann, G.; Steffen, E., Chromatic-index-critical of orders 11 and 12, European J. Combin., 19, 889-900 (1998) · Zbl 0918.05050
[5] Li, X., Lower bounds on edge critical graphs with maximum degree of 7, 8 and 9, Adv. Appl. Discrete Math., 5, 2, 97-113 (2010), India · Zbl 1216.05033
[6] Li, X., A new lower bound on critical graphs with maximum degree of 8 and 9, Ars Combin., 98, 241-257 (2011) · Zbl 1249.05125
[7] Li, S.; Li, X., Edge coloring of graphs with small maximum degrees, Discrete Math., 309, 4843-4852 (2009) · Zbl 1213.05092
[8] Li, X.; Wei, B., An improved lower bond on edge critical graphs with maximum degree of 8 and 9, Adv. Appl. Discrete Math., 12, 1, 1-38 (2013), India · Zbl 1290.05077
[9] Luo, R.; Miao, L.; Zhao, Y., The size of edge chromatic critical graphs with maximum degree 6, J. Graph Theory, 60, 149-171 (2009) · Zbl 1247.05083
[10] Miao, L.-Y.; Song, W.-Y.; Pang, S.-Y.; Miao, Z.-K., On the size of critical graphs with small maximum degree, Int. J. Comput. Math. (2014), March
[11] Sanders, D.; Zhao, Y., Planar graphs of maximum degree seven are class I, J. Combin. Theory Ser. B, 83, 2, 201-212 (2001) · Zbl 1024.05031
[12] Sanders, D.; Zhao, Y., Coloring edges of graphs embedded in a surface of characteristic zero, J. Combin. Theory Ser. B, 87, 254-263 (2003) · Zbl 1068.05026
[13] Vizing, V. G., On an estimate of the chromatic class of a \(p\)-graph, Metody Diskret. Anal., 3, 25-30 (1964)
[14] Vizing, V. G., Some unsolved problems in graph theory, Uspekhi Mat. Nauk, 23, 117-134 (1968), (in Russian); English translation in Russian Math. Surveys, 23 (1968) 125-141 · Zbl 0177.52301
[15] Woodall, D., The average degree of an edge-chromatic critical graph. II, J. Graph Theory, 56, 3, 194-218 (2007) · Zbl 1137.05037
[16] Woodall, D., The average degree of an edge-chromatic critical graph, Discrete Math., 308, 5-6, 803-819 (2008) · Zbl 1133.05035
[17] Zhang, L., Every planar graph with maximum degree 7 is of class 1, Graphs Combin., 16, 4, 467-495 (2000) · Zbl 0988.05042
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.