Skip to search boxSkip to navigationSkip to main content

Independence number of edge-chromatic critical graphs

  • Yan Cao
    ,
  • Guantao Chen
    ,
  • Guangming Jing
    ,
  • Songling Shan(corresponding author)
*Corresponding author for this work
  • West Virginia University
    ,
  • Georgia State University
    ,
  • Illinois State University
Scholary Output:
Contribution to journal
Article
 Peer-review

Abstract

Let (Formula presented.) be a simple graph with maximum degree (Formula presented.) and chromatic index (Formula presented.). A classical result of Vizing shows that either (Formula presented.) or (Formula presented.). A simple graph (Formula presented.) is called edge- (Formula presented.) -critical if (Formula presented.) is connected, (Formula presented.) and (Formula presented.) for every (Formula presented.). Let (Formula presented.) be an (Formula presented.) -vertex edge- (Formula presented.) -critical graph. Vizing conjectured that (Formula presented.), the independence number of (Formula presented.), is at most (Formula presented.). The current best result on this conjecture, shown by Woodall, is (Formula presented.). We show that for any given (Formula presented.), there exist positive constants (Formula presented.) and (Formula presented.) such that if (Formula presented.) is an (Formula presented.) -vertex edge- (Formula presented.) -critical graph with minimum degree at least (Formula presented.) and maximum degree at least (Formula presented.), then (Formula presented.). In particular, we show that if (Formula presented.) is an (Formula presented.) -vertex edge- (Formula presented.) -critical graph with minimum degree at least (Formula presented.) and (Formula presented.), then (Formula presented.).

Publication Information

Output type

Scholary Output:
Contribution to journal
Article
 Peer-review

Original language

English (US)

Pages from-to (Number of pages)

Pages 288-310 (23 pages)

Journal (Volume, Issue Number)

Journal of Graph Theory (Volume 101, Issue 2)

Publication milestones

  • Accepted/In press - 2022
  • Published - 10/2022

Publication status

Published - 10/2022

ISSN

0364-9024

Publication IDs

  • Scopus: 85126735510

Access to documents

Publication metrics

Metrics

Scopus
citations
1, opens in new tab
Fractional count
1
Fractional count
0.25
Fractional count
3
Fractional count
0.75
Fractional count
1
Fractional count
1

PlumX, opens in new tab

Captures
3
Citation count
1

Funding Details

The authors are extremely grateful to the two anonymous referees for their careful reading and valuable comments. Guantao Chen and Guangming Jing were supported by National Science Foundation grants DMS‐1855716 and DMS‐2001130, respectively.