The overfull conjecture on split-comparability and split-interval graphs
By Vizing's well-known edge coloring theorem the chromatic index \(\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 maximum degree 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. \textit{A. G. Chetwynd} and \textit{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, \textit{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 chordal graphs: graphs which are both split graphs and interval graphs, and graphs which are both split graphs and comparability graphs. 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.
- On class 2 split graphs
- Recent progress on edge-colouring graphs
- Two conjectures on edge-colouring
- Publication:4489142
- Vertex-splitting and chromatic index critical graphs
- How to find overfull subgraphs in graphs with large maximum degree. II
- Edge coloring graphs with large minimum degree
- Cores of class II graphs
- The overfull conjecture and the conformability conjecture
- A Characterization of Comparability Graphs and of Interval Graphs
- Characterizing and edge-colouring split-indifference graphs
- Complexity-separating graph classes for vertex, edge and total colouring
- Decompositions for edge-coloring join graphs and cobipartite graphs
- Edge and total coloring of interval graphs
- Edge-coloring of split graphs.
- Graphs which are vertex-critical with respect to the edge-chromatic number
- scientific article; zbMATH DE number 3910422 (Why is no real title available?)
- scientific article; zbMATH DE number 3632548 (Why is no real title available?)
- scientific article; zbMATH DE number 1463393 (Why is no real title available?)
- scientific article; zbMATH DE number 1512684 (Why is no real title available?)
- scientific article; zbMATH DE number 749267 (Why is no real title available?)
- On colorings of split graphs
- The chromatic index of complete multipartite graphs
- The chromatic index of graphs of even order with many edges
- The chromatic index of graphs with a spanning star
- The chromatic index of graphs with large maximum degree
- The NP-completeness column: an ongoing guide
- The NP-Completeness of Edge-Coloring
- Total-chromatic number and chromatic index of dually chordal graphs
This page was built for publication: The overfull conjecture on split-comparability and split-interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6048434)
