About: High-Girth Cubic Graphs are Homomorphic to the Clebsch Graph

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: High-Girth Cubic Graphs are Homomorphic to the Clebsch Graph Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://dx.doi.org/10.1002/jgt.20580
Description	We give a (computer assisted) proof that the edges of every graph with maximum degree 3 and girth at least 17 may be 5-colored (possibly improperly) so that the complement of each color class is bipartite. Equivalently, every such graph admits a homomorphism to the Clebsch graph (Fig. 1). Hopkins and Staton [J Graph Theory 6(2) (1982), 115-121] and Bondy and Locke [J Graph Theory 10(4) (1986), 477-504] proved that every (sub)cubic graph of girth at least 4/5 has an edge-cut containing at least of the edges. The existence of such an edge-cut follows immediately from the existence of a 5-edge-coloring as described above; so our theorem may be viewed as a coloring extension of their result (under a stronger girth assumption). Every graph which has a homomorphism to a cycle of length five has an above-described 5-edge-coloring; hence our theorem may also be viewed as a weak version of Nesetril''s Pentagon Problem (which asks whether every cubic graph of sufficiently high girth is homomorphic to C(5)). We give a (computer assisted) proof that the edges of every graph with maximum degree 3 and girth at least 17 may be 5-colored (possibly improperly) so that the complement of each color class is bipartite. Equivalently, every such graph admits a homomorphism to the Clebsch graph (Fig. 1). Hopkins and Staton [J Graph Theory 6(2) (1982), 115-121] and Bondy and Locke [J Graph Theory 10(4) (1986), 477-504] proved that every (sub)cubic graph of girth at least 4/5 has an edge-cut containing at least of the edges. The existence of such an edge-cut follows immediately from the existence of a 5-edge-coloring as described above; so our theorem may be viewed as a coloring extension of their result (under a stronger girth assumption). Every graph which has a homomorphism to a cycle of length five has an above-described 5-edge-coloring; hence our theorem may also be viewed as a weak version of Nesetril''s Pentagon Problem (which asks whether every cubic graph of sufficiently high girth is homomorphic to C(5)). (en)
Title	High-Girth Cubic Graphs are Homomorphic to the Clebsch Graph High-Girth Cubic Graphs are Homomorphic to the Clebsch Graph (en)
skos:prefLabel	High-Girth Cubic Graphs are Homomorphic to the Clebsch Graph High-Girth Cubic Graphs are Homomorphic to the Clebsch Graph (en)
skos:notation	RIV/00216208:11320/11:10100998!RIV12-GA0-11320___
http://linked.open...avai/predkladatel	Matematicko-fyzikální fakulta
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1M0545), P(GPP201/10/P337), Z(MSM0021620838)
http://linked.open...iv/cisloPeriodika	3
http://linked.open...vai/riv/dodaniDat	2012
http://linked.open...aciTvurceVysledku	Šámal, Robert
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	202067
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/11:10100998
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Graph; Clebsch; Homomorphic; are; Graphs; Cubic; High-Girth (en)
http://linked.open.../riv/klicoveSlovo	Graph are Clebsch Cubic Graphs High-Girth Homomorphic
http://linked.open...odStatuVydavatele	US - Spojené státy americké
http://linked.open...ontrolniKodProRIV	[7A1F33851113]
http://linked.open...i/riv/nazevZdroje	Journal of Graph Theory
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science Flows and cycles in graphs using mappings between graphs
http://linked.open...UplatneniVysledku	2011
http://linked.open...v/svazekPeriodika	66
http://linked.open...iv/tvurceVysledku	Šámal, Robert DeVos, Matt
http://linked.open...ain/vavai/riv/wos	000287676100005
http://linked.open...n/vavai/riv/zamer	Moderní metody, struktury a systémy informatiky
issn	0364-9024
number of pages	19 (xsd:int)
http://bibframe.org/vocab/doi	10.1002/jgt.20580
http://localhost/t...ganizacniJednotka	11320
is http://linked.open...avai/riv/vysledek of	High-Girth Cubic Graphs are Homomorphic to the Clebsch Graph High-Girth Cubic Graphs are Homomorphic to the Clebsch Graph

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 41 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software