|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
27 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Overfullness of critical class 2 graphs with a small core degree | | Yan Cao
; Guantao Chen
; Songling Shan
; | | Date: |
18 Aug 2020 | | Abstract: | Let $G$ be a simple graph, and let $n$, $Delta(G)$ and $chi’ (G)$ be the
order, the maximum degree and the chromatic index of $G$, respectively. We call
$G$ overfull if $|E(G)|/lfloor n/2
floor > Delta(G)$, and critical if
$chi’(H) < chi’(G)$ for every proper subgraph $H$ of $G$. Clearly, if $G$ is
overfull then $chi’(G) = Delta(G)+1$. The core of $G$, denoted by
$G_{Delta}$, is the subgraph of $G$ induced by all its maximum degree
vertices. Hilton and Zhao conjectured that for any critical class 2 graph $G$
with $Delta(G) ge 4$, if the maximum degree of $G_{Delta}$ is at most two,
then $G$ is overfull, which in turn gives $Delta(G) > n/2 +1$. We show that
for any critical class 2 graph $G$, if the minimum degree of $G_{Delta}$ is at
most two and $Delta(G) > n/2 +1$, then $G$ is overfull. | | Source: | arXiv, 2008.08135 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER