Eintrag weiter verarbeiten
Normal edge‐colorings of cubic graphs
Gespeichert in:
Zeitschriftentitel: | Journal of Graph Theory |
---|---|
Personen und Körperschaften: | , |
In: | Journal of Graph Theory, 94, 2020, 1, S. 75-91 |
Format: | E-Article |
Sprache: | Englisch |
veröffentlicht: |
Wiley
|
Schlagwörter: |
author_facet |
Mazzuoccolo, Giuseppe Mkrtchyan, Vahan Mazzuoccolo, Giuseppe Mkrtchyan, Vahan |
---|---|
author |
Mazzuoccolo, Giuseppe Mkrtchyan, Vahan |
spellingShingle |
Mazzuoccolo, Giuseppe Mkrtchyan, Vahan Journal of Graph Theory Normal edge‐colorings of cubic graphs Geometry and Topology Discrete Mathematics and Combinatorics |
author_sort |
mazzuoccolo, giuseppe |
spelling |
Mazzuoccolo, Giuseppe Mkrtchyan, Vahan 0364-9024 1097-0118 Wiley Geometry and Topology Discrete Mathematics and Combinatorics http://dx.doi.org/10.1002/jgt.22507 <jats:title>Abstract</jats:title><jats:p>A normal ‐edge‐coloring of a cubic graph is a proper edge‐coloring with colors having the additional property that when looking at the set of colors assigned to any edge and the four edges adjacent to it, we have either exactly five distinct colors or exactly three distinct colors. We denote by the smallest , for which admits a normal ‐edge‐coloring. Normal ‐edge‐colorings were introduced by Jaeger to study his well‐known Petersen Coloring Conjecture. More precisely, it is known that proving for every bridgeless cubic graph is equivalent to proving the Petersen Coloring Conjecture and then it implies, among others, Cycle Double Cover Conjecture and Berge‐Fulkerson Conjecture. Considering the larger class of all simple cubic graphs (not necessarily bridgeless), some interesting questions naturally arise. For instance, there exist simple cubic graphs, not bridgeless, with . In contrast, the known best general upper bound for was . Here, we improve it by proving that for any simple cubic graph , which is best possible. We obtain this result by proving the existence of specific nowhere zero ‐flows in ‐edge‐connected graphs.</jats:p> Normal edge‐colorings of cubic graphs Journal of Graph Theory |
doi_str_mv |
10.1002/jgt.22507 |
facet_avail |
Online |
finc_class_facet |
Informatik Mathematik |
format |
ElectronicArticle |
fullrecord |
blob:ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTAwMi9qZ3QuMjI1MDc |
id |
ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTAwMi9qZ3QuMjI1MDc |
institution |
DE-15 DE-Pl11 DE-Rs1 DE-14 DE-105 DE-Ch1 DE-L229 DE-D275 DE-Bn3 DE-Brt1 DE-D161 DE-Zi4 DE-Gla1 |
imprint |
Wiley, 2020 |
imprint_str_mv |
Wiley, 2020 |
issn |
0364-9024 1097-0118 |
issn_str_mv |
0364-9024 1097-0118 |
language |
English |
mega_collection |
Wiley (CrossRef) |
match_str |
mazzuoccolo2020normaledgecoloringsofcubicgraphs |
publishDateSort |
2020 |
publisher |
Wiley |
recordtype |
ai |
record_format |
ai |
series |
Journal of Graph Theory |
source_id |
49 |
title |
Normal edge‐colorings of cubic graphs |
title_unstemmed |
Normal edge‐colorings of cubic graphs |
title_full |
Normal edge‐colorings of cubic graphs |
title_fullStr |
Normal edge‐colorings of cubic graphs |
title_full_unstemmed |
Normal edge‐colorings of cubic graphs |
title_short |
Normal edge‐colorings of cubic graphs |
title_sort |
normal edge‐colorings of cubic graphs |
topic |
Geometry and Topology Discrete Mathematics and Combinatorics |
url |
http://dx.doi.org/10.1002/jgt.22507 |
publishDate |
2020 |
physical |
75-91 |
description |
<jats:title>Abstract</jats:title><jats:p>A normal ‐edge‐coloring of a cubic graph is a proper edge‐coloring with colors having the additional property that when looking at the set of colors assigned to any edge and the four edges adjacent to it, we have either exactly five distinct colors or exactly three distinct colors. We denote by the smallest , for which admits a normal ‐edge‐coloring. Normal ‐edge‐colorings were introduced by Jaeger to study his well‐known Petersen Coloring Conjecture. More precisely, it is known that proving for every bridgeless cubic graph is equivalent to proving the Petersen Coloring Conjecture and then it implies, among others, Cycle Double Cover Conjecture and Berge‐Fulkerson Conjecture. Considering the larger class of all simple cubic graphs (not necessarily bridgeless), some interesting questions naturally arise. For instance, there exist simple cubic graphs, not bridgeless, with . In contrast, the known best general upper bound for was . Here, we improve it by proving that for any simple cubic graph , which is best possible. We obtain this result by proving the existence of specific nowhere zero ‐flows in ‐edge‐connected graphs.</jats:p> |
container_issue |
1 |
container_start_page |
75 |
container_title |
Journal of Graph Theory |
container_volume |
94 |
format_de105 |
Article, E-Article |
format_de14 |
Article, E-Article |
format_de15 |
Article, E-Article |
format_de520 |
Article, E-Article |
format_de540 |
Article, E-Article |
format_dech1 |
Article, E-Article |
format_ded117 |
Article, E-Article |
format_degla1 |
E-Article |
format_del152 |
Buch |
format_del189 |
Article, E-Article |
format_dezi4 |
Article |
format_dezwi2 |
Article, E-Article |
format_finc |
Article, E-Article |
format_nrw |
Article, E-Article |
_version_ |
1792342529470889984 |
geogr_code |
not assigned |
last_indexed |
2024-03-01T16:36:44.376Z |
geogr_code_person |
not assigned |
openURL |
url_ver=Z39.88-2004&ctx_ver=Z39.88-2004&ctx_enc=info%3Aofi%2Fenc%3AUTF-8&rfr_id=info%3Asid%2Fvufind.svn.sourceforge.net%3Agenerator&rft.title=Normal+edge%E2%80%90colorings+of+cubic+graphs&rft.date=2020-05-01&genre=article&issn=1097-0118&volume=94&issue=1&spage=75&epage=91&pages=75-91&jtitle=Journal+of+Graph+Theory&atitle=Normal+edge%E2%80%90colorings+of+cubic+graphs&aulast=Mkrtchyan&aufirst=Vahan&rft_id=info%3Adoi%2F10.1002%2Fjgt.22507&rft.language%5B0%5D=eng |
SOLR | |
_version_ | 1792342529470889984 |
author | Mazzuoccolo, Giuseppe, Mkrtchyan, Vahan |
author_facet | Mazzuoccolo, Giuseppe, Mkrtchyan, Vahan, Mazzuoccolo, Giuseppe, Mkrtchyan, Vahan |
author_sort | mazzuoccolo, giuseppe |
container_issue | 1 |
container_start_page | 75 |
container_title | Journal of Graph Theory |
container_volume | 94 |
description | <jats:title>Abstract</jats:title><jats:p>A normal ‐edge‐coloring of a cubic graph is a proper edge‐coloring with colors having the additional property that when looking at the set of colors assigned to any edge and the four edges adjacent to it, we have either exactly five distinct colors or exactly three distinct colors. We denote by the smallest , for which admits a normal ‐edge‐coloring. Normal ‐edge‐colorings were introduced by Jaeger to study his well‐known Petersen Coloring Conjecture. More precisely, it is known that proving for every bridgeless cubic graph is equivalent to proving the Petersen Coloring Conjecture and then it implies, among others, Cycle Double Cover Conjecture and Berge‐Fulkerson Conjecture. Considering the larger class of all simple cubic graphs (not necessarily bridgeless), some interesting questions naturally arise. For instance, there exist simple cubic graphs, not bridgeless, with . In contrast, the known best general upper bound for was . Here, we improve it by proving that for any simple cubic graph , which is best possible. We obtain this result by proving the existence of specific nowhere zero ‐flows in ‐edge‐connected graphs.</jats:p> |
doi_str_mv | 10.1002/jgt.22507 |
facet_avail | Online |
finc_class_facet | Informatik, Mathematik |
format | ElectronicArticle |
format_de105 | Article, E-Article |
format_de14 | Article, E-Article |
format_de15 | Article, E-Article |
format_de520 | Article, E-Article |
format_de540 | Article, E-Article |
format_dech1 | Article, E-Article |
format_ded117 | Article, E-Article |
format_degla1 | E-Article |
format_del152 | Buch |
format_del189 | Article, E-Article |
format_dezi4 | Article |
format_dezwi2 | Article, E-Article |
format_finc | Article, E-Article |
format_nrw | Article, E-Article |
geogr_code | not assigned |
geogr_code_person | not assigned |
id | ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTAwMi9qZ3QuMjI1MDc |
imprint | Wiley, 2020 |
imprint_str_mv | Wiley, 2020 |
institution | DE-15, DE-Pl11, DE-Rs1, DE-14, DE-105, DE-Ch1, DE-L229, DE-D275, DE-Bn3, DE-Brt1, DE-D161, DE-Zi4, DE-Gla1 |
issn | 0364-9024, 1097-0118 |
issn_str_mv | 0364-9024, 1097-0118 |
language | English |
last_indexed | 2024-03-01T16:36:44.376Z |
match_str | mazzuoccolo2020normaledgecoloringsofcubicgraphs |
mega_collection | Wiley (CrossRef) |
physical | 75-91 |
publishDate | 2020 |
publishDateSort | 2020 |
publisher | Wiley |
record_format | ai |
recordtype | ai |
series | Journal of Graph Theory |
source_id | 49 |
spelling | Mazzuoccolo, Giuseppe Mkrtchyan, Vahan 0364-9024 1097-0118 Wiley Geometry and Topology Discrete Mathematics and Combinatorics http://dx.doi.org/10.1002/jgt.22507 <jats:title>Abstract</jats:title><jats:p>A normal ‐edge‐coloring of a cubic graph is a proper edge‐coloring with colors having the additional property that when looking at the set of colors assigned to any edge and the four edges adjacent to it, we have either exactly five distinct colors or exactly three distinct colors. We denote by the smallest , for which admits a normal ‐edge‐coloring. Normal ‐edge‐colorings were introduced by Jaeger to study his well‐known Petersen Coloring Conjecture. More precisely, it is known that proving for every bridgeless cubic graph is equivalent to proving the Petersen Coloring Conjecture and then it implies, among others, Cycle Double Cover Conjecture and Berge‐Fulkerson Conjecture. Considering the larger class of all simple cubic graphs (not necessarily bridgeless), some interesting questions naturally arise. For instance, there exist simple cubic graphs, not bridgeless, with . In contrast, the known best general upper bound for was . Here, we improve it by proving that for any simple cubic graph , which is best possible. We obtain this result by proving the existence of specific nowhere zero ‐flows in ‐edge‐connected graphs.</jats:p> Normal edge‐colorings of cubic graphs Journal of Graph Theory |
spellingShingle | Mazzuoccolo, Giuseppe, Mkrtchyan, Vahan, Journal of Graph Theory, Normal edge‐colorings of cubic graphs, Geometry and Topology, Discrete Mathematics and Combinatorics |
title | Normal edge‐colorings of cubic graphs |
title_full | Normal edge‐colorings of cubic graphs |
title_fullStr | Normal edge‐colorings of cubic graphs |
title_full_unstemmed | Normal edge‐colorings of cubic graphs |
title_short | Normal edge‐colorings of cubic graphs |
title_sort | normal edge‐colorings of cubic graphs |
title_unstemmed | Normal edge‐colorings of cubic graphs |
topic | Geometry and Topology, Discrete Mathematics and Combinatorics |
url | http://dx.doi.org/10.1002/jgt.22507 |