Applications of edge coloring of multigraphs to vertex coloring of graphs (Q1121898): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
Import240304020342 (talk | contribs)
Set profile property.
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank

Revision as of 02:16, 5 March 2024

scientific article
Language Label Description Also known as
English
Applications of edge coloring of multigraphs to vertex coloring of graphs
scientific article

    Statements

    Applications of edge coloring of multigraphs to vertex coloring of graphs (English)
    0 references
    0 references
    1989
    0 references
    If G is a graph which induces neither \(K_{1,3}\) nor \(K_{2s+3}-e\), and the maximum clique size \(\omega\) (G) is sufficiently large then \(\chi (G)\leq \omega (G)+s.\) The proof relies on showing a correspondence between vertex coloring G and edge coloring a certain multigraph and then applying a previous result on edge coloring. The author hopes that his work will stimulate research on edge coloring multigraphs by showing how chromatic index bounds for multigraphs can be used to derive results on chromatic number. A number of interesting problems and conjectures are also proposed.
    0 references
    multigraph
    0 references
    chromatic index
    0 references
    chromatic number
    0 references
    0 references

    Identifiers