|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Sparse $4$-critical graphs have low circular chromatic number | | Benjamin Moore
; | | Date: |
30 Jul 2020 | | Abstract: | Kostochka and Yancey proved that every $4$-critical graph $G$ has $e(G) geq
frac{5v(G) - 2}{3}$, and that equality holds if and only if $G$ is $4$-Ore. We
show that a question of Postle and Smith-Roberge implies that every
$4$-critical graph with no $(7,2)$-circular-colouring has $e(G) geq
frac{27v(G) -20}{15}$. We prove that every $4$-critical graph with no
$(7,2)$-colouring has $e(G) geq frac{17v(G)}{10}$ unless $G$ is isomorphic to
$K_{4}$ or the wheel on six vertices. We also show that if the Gallai Tree of a
$4$-critical graph with no $(7,2)$-colouring has every component isomorphic to
either an odd cycle, a claw, or a path. In the case that the Gallai Tree
contains an odd cycle component, then $G$ is isomorphic to an odd wheel. In
general, we show a $k$-critical graph with no $(2k-1,2)$-colouring that
contains a clique of size $k-1$ in it’s Gallai Tree is isomorphic to $K_{k}$. | | Source: | arXiv, 2007.15556 | | 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