×
da Soledade Gonzaga, Luis Gustavo; Bismarck de Sousa Cruz, Jadder; Morais de Almeida, Sheila; Nunes da Silva, Cândida

The overfull conjecture on split-comparability and split-interval graphs. (English) Zbl 1527.05064

Discrete Appl. Math. 340, 228-238 (2023).
By Vizing’s well-known edge coloring theorem the \(\chi^\prime(G)\) of a graph \(G\) satisfies \(\chi^\prime(G) =\Delta(G)\) or \(\chi^\prime(G) = \Delta(G)+1\), where \(\Delta(G)\) as usual denotes the of a graph \(G\). Graphs with chromatic index \(\Delta(G)\) are called Class 1, and those with \(\Delta(G)+1\) are called Class 2. A graph \(G\) is overfull if it has more than \(\Delta(G) \lfloor |V(G)| /2 \rfloor\) edges; such graphs are Class 2.
A graph \(G\) is subgraph-overfull if it has a subgraph \(H\) such that \(\Delta(H) = \Delta(G)\) and \(H\) is overfull. \(G\) is neighborhood-overfull if some vertex of maximum degree satisfies that the subgraph induced by its closed neighborhood is overfull.
A. G. Chetwynd and A. J. W. Hilton [J. Graph Theory 8, 463–470 (1984; Zbl 0562.05024)] conjectured that if \(G\) is a graph with \(\Delta(G) > |V(G)|/3\), then \(G\) is Class 1 if and only if it is not subgraph-overfull. Later on, C. M. H. de Figueiredo et al. [J. Comb. Math. Comb. Comput. 32, 79–91 (2000; Zbl 0981.05045)] conjectured that if \(G\) is chordal, then it is Class 1 if and only if it is not subgraph-overfull.
In the paper under review, the authors verify that both conjectures hold for two families of : graphs which are both and , and graphs which are both split graphs and . The proofs of the results are based on the structural properties of these classes and yield polynomial-time algorithms for deciding whether a graph from these families is Class 1 or Class 2.
Reviewer: Carl Casselgren (Linköping)

Cited in 2 Documents

MSC:

05C15 Coloring of graphs and hypergraphs
05C75 Structural characterization of families of graphs
05C85 Graph algorithms (graph-theoretic aspects)

Keywords:

edge coloring; chromatic index; chordal graph; split graph; interval graph; comparability graph

Citations:

Zbl 0562.05024; Zbl 0981.05045
Cite Review PDF
Full Text: DOI

References:

[1] Almeida, S. M.d., Coloração de Arestas em Grafos Split, 2012, Universidade Estadual de Campinas: Universidade Estadual de Campinas Campinas, (Ph.D. thesis)
[2] Almeida, S. M.; De Mello, C. P.; Morgana, A., On the classification problem for split graphs, J. Braz. Comput. Soc., 18, 2, 95-101, 2012
[3] Almeida, S.; Picinin, C., Edge-coloring of split graphs, Ars Combin., 2015
[4] Bender, E. A.; Richmond, L. B.; Wormald, N. C., Almost all chordal graphs split, J. Aust. Math. Soc. A, 38, 2, 214-221, 1985 · Zbl 0571.05026
[5] Bojarshinov, V. A., Edge and total coloring of interval graphs, Discrete Appl. Math., 114, 1–3, 23-28, 2001 · Zbl 0996.05052
[6] Chen, B.; Fu, H.; Ko, M. T., Total chromatic number and chromatic index of split graphs, J. Combin. Math. Combin. Comput., 17, 1995 · Zbl 0819.05026
[7] Chetwynd, A. G.; Hilton, A. J.W., The chromatic index of graphs of even order with many edges, J. Graph Theory, 8, 4, 463-470, 1984 · Zbl 0562.05024
[8] Chetwynd, A. G.; Hilton, A. J.W., Star multigraphs with three vertices of maximum degree, 303-317
[9] de Figueiredo, C. M.H., Complexity-separating graph classes for vertex, edge and total colouring, Discrete Appl. Math., 281, 162-171, 2020 · Zbl 1440.05188
[10] De Figueiredo, C. M.H.; Meidanis, J.; de Mello, C. P., Total-chromatic number and chromatic index of dually chordal graphs, Inform. Process. Lett., 70, 3, 147-152, 1999 · Zbl 1339.05151
[11] de Figueiredo, C. M.; Meidanis, J.; de Mello, C. P., Local conditions for edge-coloring, J. Combin. Math. Combin. Comput., 32, 79-92, 2000 · Zbl 0981.05045
[12] de Figueiredo, C. M.H.; de Mello, C. P.; Ortiz, C., Edge colouring reduced indifference graphs, 145-153 · Zbl 0994.05064
[13] Gilmore, P. C.; Hoffman, A. J., A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, 539-548, 1964 · Zbl 0121.26003
[14] Hammer, P. L.; Földes, S., Split graphs, Congr. Numer., 19, 311-315, 1977 · Zbl 0407.05071
[15] Hilton, A. J.W.; Johnson, P. D., Graphs which are vertex-critical with respect to the edge-chromatic number, 211-221 · Zbl 0631.05024
[16] Hoffman, D. G.; Rodger, C. A., The chromatic index of complete multipartite graphs, J. Graph Theory, 16, 159-163, 1992 · Zbl 0760.05041
[17] Holyer, I., The NP-completeness of edge-coloring, SIAM J. Comput., 10, 4, 718-720, 1981 · Zbl 0473.68034
[18] Johnson, D. S., The NP-completeness column: an ongoing guide, J. Algorithms, 6, 3, 434-451, 1985 · Zbl 0608.68032
[19] Machado, R. C.S.; de Figueiredo, C. M.H., Decompositions for edge-coloring join graphs and cobipartite graphs, Discrete Appl. Math., 158, 12, 1336-1342, 2010 · Zbl 1218.05050
[20] Ortiz, C.; Maculan, N.; Szwarcfiter, J. L., Characterizing and edge-colouring split-indifference graphs, Discrete Appl. Math., 82, 1–3, 209-217, 1998 · Zbl 0901.05043
[21] C. Ortiz, M. Villanueva, On split-comparability graphs, in: Proc. II ALIO-EURO Workshop on Practical Combinatorial Optimization, Valparaiso, Chile, 1996, pp. 91–105.
[22] Plantholt, M., The chromatic index of graphs with a spanning star, J. Graph Theory, 5, 1, 45-53, 1981 · Zbl 0448.05031
[23] Plantholt, M. J., The chromatic index of graphs with large maximum degree, Discrete Math., 47, 91-96, 1983 · Zbl 0528.05028
[24] Tan, N. D.; Hung, L. X., On colorings of split graphs, Acta Math. Vietnam., 31, 3, 195-204, 2006 · Zbl 1133.05034
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.